[Question]
  [
This [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'") challenge will give you an integer `n`, and ask you to count the number of positive integer sequences \$S = (a\_1, a\_2, \dots, a\_t)\$ such that
1. \$a\_1 + a\_2 + \cdots + a\_t = n\$, and
2. \$\displaystyle
\sqrt{a\_1+\sqrt{a\_2 + \cdots + \stackrel{\vdots}{\sqrt{a\_t}}}}
\$ is an integer.
### Example
If `n = 14`, then there are 8 such sequences:
* \$\sqrt{2+\sqrt{2+\sqrt{2+\sqrt{2+\sqrt{2+\sqrt{3+\sqrt{1}}}}}}} = 2\$
* \$\sqrt{2+\sqrt{2+\sqrt{2+\sqrt{2+\sqrt{2+\sqrt{4}}}}}} = 2\$
* \$\sqrt{1+\sqrt{7+\sqrt{2+\sqrt{3+\sqrt{1}}}}} = 2\$
* \$\sqrt{2+\sqrt{1+\sqrt{7+\sqrt{3+\sqrt{1}}}}} = 2\$
* \$\sqrt{2+\sqrt{2+\sqrt{1+\sqrt{8+\sqrt{1}}}}} = 2\$
* \$\sqrt{1+\sqrt{7+\sqrt{2+\sqrt{4}}}} = 2\$
* \$\sqrt{2+\sqrt{1+\sqrt{7+\sqrt{4}}}} = 2\$
* \$\sqrt{2+\sqrt{2+\sqrt{1+\sqrt{9}}}} = 2\$
(In this example, all of the nested square root expressions are equal to 2, but in general, this may not be the case.)
Pairs \$(n,(a(n))\$ for \$n \leq 25\$:
```
(1,1),(2,0),(3,0),(4,2),(5,0),(6,2),(7,0),(8,2),(9,2),(10,4),(11,2),(12,6),(13,2),(14,8),(15,4),(16,14),(17,6),(18,20),(19,8),(20,28),(21,14),(22,44),(23,20),(24,66),(25,30)
```
---
Your code must be robust against floating-point errors, that is it must work for arbitrarily large inputs, in principle.
Since this is a [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'") challenge, the shortest code wins.
---
(This is now on the On-Line Encyclopedia of Integer Sequences as
[A338271](https://oeis.org/A338271). Sequence [A338268](https://oeis.org/A338268) has been added too, based on [Bubbler's \$f\$ function](https://codegolf.stackexchange.com/a/213851/53884).)
  
[Answer]
# [APL (Dyalog Unicode)](https://www.dyalog.com/), 39 [bytes](https://github.com/abrudz/SBCS)
```
+/⊢{∨/⍺⍵<⍵0:0⋄⍺=0:1⋄+/∊∇¨/⍺(⍵*2)-⊂⍳⍺}¨⍳
```
[Try it online!](https://tio.run/##JYy/DgFBEIf7e5I7RuzO7p0/odLQ4gUkchoJrYgG4XJyQuEFVDqFaJT3KPMiZ3a22N/vm803M1svG/PNbLlaVFW9SflzS9mrScWPim@Pn@oquhx57quuZmInyyk7lyKFbNQwalC@p@LDH7vyxVCldLpRcaX8UL4Nne50fUzGA87pcDSpUpEwDoJolaZBqEFHECIoTiNpATlj4US4JdwW7khqBdaV9hNC4sr4yULbVeyVBLR0yzt8xR3THZFQAUprbyGClTZeQwuJW8MYjIr@ "APL (Dyalog Unicode) – Try It Online")
A tacit function containing an inner dfn to use recursion. Does not use floating point numbers at all.
### How it works
First of all, observe that
$$
\displaystyle
\sqrt{a\_1+\sqrt{a\_2 + \cdots + \stackrel{\vdots}{\sqrt{a\_t}}}} \le \cdots \le \sqrt{a\_1+a\_2 + \cdots + a\_t} \le a\_1+a\_2 + \cdots + a\_t = n
$$
and this holds for all suffixes of any given sequence of positive integers.
Let's define a function \$f(x,y)\$ as the number of sequences where the sum is \$x\$ and the "root sum" is \$y\$. Then the following holds:
$$
\begin{align}
f(0, 0) &= 1 \\
f(0, y) &= 0, \qquad 0 < y \\
f(x, y) &= 0, \qquad x < y \text{ or } y < 0 \\
f(x, y) &= \sum\_{i=1}^{x}{f(x-i, y^2-i)}
\end{align}
$$
Then the desired result is the sum \$\sum\_{i=1}^{n}{f(n,i)}\$.
[Answer]
# [Python 3](https://docs.python.org/3/), 67 bytes
This builds all sequences that sum to \$n\$ and slightly higher and counts those that exactly sum to \$n\$.
```
f=lambda n,k=0:(n==0)+sum(f(n-d*d+k,d)for d in range(n-~k)if d*d>k)
```
[Try it online!](https://tio.run/##RcnBCsIwDADQu1@R2xLXwZzgodD9SyVGQ1026jzI0F@v9eTtwVte6222YykS7nE6cwRzKfQeLYSe2sdzQkHreM9tckwyZ2BQgxzteqnxSaQCtcdE5bf634OD4UR@B7BktRWl2dQPb@hG2ASVqhsqXw "Python 3 – Try It Online")
This approach is based on the observation that \$\sqrt x\$ can only be an integer if \$x\$ is an integer. This means, when building a sequence right to left, we always have to make sure to complete to a perfect square.
At every step \$\sqrt{a\_i+k}\$, \$a\_i+k = d^2\$ for some positive \$d\$ with \$0 \lt d^2-k \le n'\$, where \$n'\$ is the remaining integer at the current step. To check every possible square, \$d\$ needs to be tested up to \$\lfloor\sqrt{n'+k}\rfloor\ \le n+k\$.
In the code we count the number of times \$n'=0\$ is exactly reached, by summing all results and adding `n==0`. If `n` gets negative, `range(n-~k)` will eventually be empty, which will cause the recursion to stop.
This seems to be currently the fastest approach, and with some added *memoization* this gets really fast: [First 1000 values](https://tio.run/##RY1BDoIwEEX3nGJ2dAQS0B1JOYJXMJV2pIFOSYFEJXr1WhfGv3rJS96fH@vg@RQjyUm5q1bA5SjrVrCUNRbL5gQJrvRBF2OpkXwADZYhKL6ZJN4jWoKkuxEjBe@ANu5X76cFrJt9WGEK26VX/WCy9PFj4dR9sU8jz54NCsIs@7btv92U0NR1g20GaXOwvArKd9seX1B1sJOwmDjH@AE "Python 3 – Try It Online")
With a small modification the sequences can be printed:
```
f=lambda n,k=0,*a:(n==0!=print(a))+sum(f(n-d*d+k,d,d*d-k,*a)for d in range(n-~k)if d*d>k)
```
[Try it online!](https://tio.run/##JYwxDsIwDAC/Yja7TaUimJDMX4yMITJ1q9AOLHw9jdTphjvd8lvfc1xqNf7I9FCBSM5j6uSGwTyeeCk5VhSi/rtNaBiDdtp70tQ4eCvJ5gIKOaBIvJ6t@Dtlg@bvTvUYGJ6vRHUH "Python 3 – Try It Online")
[Answer]
# [CP-1610](https://en.wikipedia.org/wiki/General_Instrument_CP1600) machine code, 31 DECLEs1 ≈ 39 bytes2
*1. A CP-1610 opcode is encoded with a 10-bit value (0x000 to 0x3FF), known as a 'DECLE'.*  
*2. As per the exception described [in this meta answer](https://codegolf.meta.stackexchange.com/a/10810/58563), the exact score is **38.75 bytes** (310 bits)*
---
This is an implementation with only integer additions, subtractions and comparisons.
A routine taking the input in **R1** and returning the result in **R3**.
```
**1DB**  |         CLRR    R3
**1C0**  |         CLRR    R0
**275**  | @@rec   PSHR    R5
**089**  |         TSTR    R1
**20C 001**  |         BNEQ    @@notZ
**00B**  |         INCR    R3
**272**  | @@notZ  PSHR    R2
**1D2**  |         CLRR    R2
**110**  | @@loop  SUBR    R2,     R0
**012**  |         DECR    R2
**110**  |         SUBR    R2,     R0
**148**  |         CMPR    R1,     R0
**20E 00E**  |         BGT     @@done
**080**  |         TSTR    R0
**226 008**  |         BLE     @@loop
**270**  |         PSHR    R0
**271**  |         PSHR    R1
**101**  |         SUBR    R0,     R1
**090**  |         MOVR    R2,     R0
**004 148 040** |         CALL    @@rec
**2B1**  |         PULR    R1
**2B0**  |         PULR    R0
**220 013**  |         B       @@loop
**2B2**  | @@done  PULR    R2
**2B7**  |         PULR    R7
```
### Full commented test code
```
        ROMW    10                ; use 10-bit ROM width
        ORG     $4800             ; map this program at $4800
PNUM    QEQU    $18C5             ; EXEC routine: print a number
        ;; ------------------------------------------------------------- ;;
        ;;  main code                                                    ;;
        ;; ------------------------------------------------------------- ;;
main    PROC
        SDBD                      ; set up an interrupt service routine
        MVII    #isr,   R0        ; to do some minimal STIC initialization
        MVO     R0,     $100
        SWAP    R0
        MVO     R0,     $101
        EIS                       ; enable interrupts
        MVII    #$200,  R3        ; R3 = backtab pointer
        CLRR    R1                ; R1 = number to test
@@loop  INCR    R1                ; increment R1
        PSHR    R1                ; save R1 & R3 on the stack
        PSHR    R3
        CALL    func              ; invoke our routine
        MOVR    R3,     R1        ; save the result in R1
        PULR    R3                ; restore R3
        CALL    print             ; print R1
        PULR    R1                ; restore R1
        CMPI    #28,    R1        ; go on as long as R1 is less than 28
        BLT     @@loop
        DECR    R7                ; done: loop forever
        ENDP
        ;; ------------------------------------------------------------- ;;
        ;;  prints the result of a test case                             ;;
        ;; ------------------------------------------------------------- ;;
print   PROC
        PSHR    R5                ; save the return address on the stack
        MOVR    R1,     R0        ; R0 = number to print
        MVII    #4,     R1        ; R1 = number of digits
        MOVR    R3,     R4        ; R4 = backtab pointer
        ADDI    #5,     R3        ; advance by 5 characters for the next one
        PSHR    R3                ; save R3
        CLRR    R3                ; R3 = attributes (black)
        CALL    PNUM              ; invoke the EXEC routine
        PULR    R3                ; restore R3
        PULR    R7                ; return
        ENDP
        ;; ------------------------------------------------------------- ;;
        ;;  ISR                                                          ;;
        ;; ------------------------------------------------------------- ;;
isr     PROC
        MVO     R0,     $0020     ; enable display
        MVI     $0021,  R0        ; colorstack mode
        CLRR    R0
        MVO     R0,     $0030     ; no horizontal delay
        MVO     R0,     $0031     ; no vertical delay
        MVO     R0,     $0032     ; no border extension
        MVII    #$D,    R0
        MVO     R0,     $0028     ; light-blue background
        MVO     R0,     $002C     ; light-blue border
        JR      R5                ; return from ISR
        ENDP
        ;; ------------------------------------------------------------- ;;
        ;;  our routine                                                  ;;
        ;; ------------------------------------------------------------- ;;
func    PROC
        CLRR    R3                ; R3 = counter for the final result
        CLRR    R0                ; start with R0 = 0
@@rec   PSHR    R5                ; this is the recursive entry point
        TSTR    R1                ; if R1 is equal to 0 ...
        BNEQ    @@notZ
        INCR    R3                ; ... increment R3
@@notZ  PSHR    R2                ; save R2 on the stack
        CLRR    R2                ; start with R2 = 0
@@loop  SUBR    R2,     R0        ; subtract R2 from R0
        DECR    R2                ; decrement R2
        SUBR    R2,     R0        ; subtract R2 from R0
        CMPR    R1,     R0        ; abort if R0 is greater than R1
        BGT     @@done
        TSTR    R0                ; skip the recursive call if R0 <= 0
        BLE     @@loop
        PSHR    R0                ; save R0 and R1 on the stack
        PSHR    R1
        SUBR    R0,     R1        ; subtract R0 from R1
        MOVR    R2,     R0        ; move R2 to R0
        CALL    @@rec             ; recursive call
        PULR    R1                ; restore R0 and R1
        PULR    R0
        B       @@loop            ; keep going
@@done  PULR    R2                ; this is either the end of a recursive
        PULR    R7                ; call or the end of the routine
        ENDP
```
### Output
Below are **a(1)** to **a(28)**.
[![output](https://i.stack.imgur.com/KmMut.png)](https://i.stack.imgur.com/KmMut.png)
*screenshot from [jzIntv](http://spatula-city.org/%7Eim14u2c/intv/)*
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), ~~56~~ 50 bytes
```
If[a=##-i i;0<a<#,a~#0~i,1-Sign@a]~Sum~{i,√+##}&
```
[Try it online!](https://tio.run/##y00syUjNTSzJTE78n2b73zMtOtFWWVk3UyHT2sAm0UZZJ7FO2aAuU8dQNzgzPc8hMbYuuDS3rjpT51HHLG1l5Vq1/wFFmXkl0cq6dmkOyrFqdY5FRYmVdUam/wE "Wolfram Language (Mathematica) – Try It Online")
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), ~~20~~ 19 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
Åœ€œ€`ÙʒÅ«t+}н§Å²}g
```
Brute-force approach, so very slow. Times out for \$\geq10\$.
[Try it online](https://tio.run/##yy9OTMpM/f//cOvRyY@a1oCJhMMzT0063HpodYl27YW9h5YDmZtq0///NwMA) or [verify the first 9 test cases](https://tio.run/##yy9OTMpM/W/p6mevpPCobZKCkr3f/8OtRyc/aloDJhIOzzw16XDrodUl2rUX9h5aDmRuqk3/r/MfAA).
**Explanation:**
```
Åœ              # Get all combinations of positive integers that sum to the (implicit)
                # input-integer
  €             # Map over each inner list:
   œ            #  And get all its permutations
    €`          # Flatten the list of lists of lists one level down
      Ù         # Uniquify the list of lists
       ʒ        # Filter it by:
        Å«      #  Cumulative left-reduce the list by:
          t     #   Taking the square of the current integer
           +    #   And adding it to the previous
         }      #  After the cumulative left-reduce, which keeps all intermediate steps:
          н     #  Pop and push its first item
           §    #  Cast this decimal to a string (bug work-around)
            Å²  #  And check that it's a perfect square
       }g       # After the filter: pop and push the length
                # (which is output implicitly as result)
```
The `§` shouldn't have been necessary, but unfortunately there is [an 05AB1E bug with decimal values for the `Å²` builtin](https://github.com/Adriandmen/05AB1E/issues/172).
[Answer]
# [Retina](https://github.com/m-ender/retina/wiki/The-Language), 65 bytes
```
.+
*_;
+%L$w`^((^_|\2__)*)(;|(?=(_+);(?!\1)))
$#4*$#2*_$4;$#2*_
;
```
[Try it online!](https://tio.run/##HcgxCoAwDADAPb8QU0haKLTUKaiji08oTR0cXBxEcPHvFZwO7trv49xC8w4srFgV0E8VDC31PxVwZsWnFqKib46qbJnkpXkkdSw0dzkwM2CfLPbRKib5BWktDh8 "Retina – Try It Online") Link includes test suite that tests all `n` up to and including the input. Explanation:
```
.+
*_;
```
Convert the input to unary and append a working area for the previous square root.
```
+`
```
Repeat until no new solutions can be found.
```
%`
```
Check all lines separately for new solutions.
```
L$w`^((^_|\2__)*)(;|(?=(_+);(?!\1)))
```
Match all square prefixes of the current value. This (`$.1`) represents the amount being square rooted on this pass. `$#2` is its square root. `$.4` is the residue after subtracting the terms so far; `$#4` is a flag for whether the residue is non-zero, in which case the square must be greater than the previous square root. This check is not performed if the residue is zero, as the previous residue must have been non-zero anyway, thus allowing completed sequences to remain undisturbed.
```
$#4*$#2*_$4;$#2*_
```
For each square prefix, add its square root to the residue, and record the new value along with the square root. However, if the current value turned out to be square, then the square root is skipped and all that remains is the `;`. This indicates a completed sequence.
```
;
```
Count the number of complete sequences found.
[Answer]
# [APL (Dyalog Unicode)](https://www.dyalog.com/), ~~35~~ 34 [bytes](https://github.com/abrudz/SBCS)
Thanks to [Bubbler](https://codegolf.stackexchange.com/users/78410/bubbler) for -1 byte!
Another port of my Python answer.
```
0∘{⍵≤⍺:⍵=⍺⋄(⊢+.∇⊢+⍵-×⍨)(⌊⍺*÷2)↓⍳⍵}
```
[Try it online!](https://tio.run/##SyzI0U2pTMzJT///3@BRx4zqR71bH3UuedS7ywrIsgXSj7pbNB51LdLWe9TRDqKBwrqHpz/qXaGp8ainC6hA6/B2I81HbZMf9W4GytX@T3vUNuFRb9@jruZHvWse9W45tN74UdvER31Tg4OcgWSIh2fw/7RDKxSA6k0NAA "APL (Dyalog Unicode) – Try It Online")
The main function is the *dfn* `{ ... }` which takes \$k\$ as the left argument and \$n+k\$ as the right argument. `0∘` supplies the initial \$k=0\$.
`⍵≤⍺:⍵=⍺` is the stopping condition, if \$n+k \le k \Leftrightarrow n \le 0\$, this returns a value of \$1\$ if \$n=0\$ and \$0\$ otherwise.
`⍳⍵` is the inclusive range from \$1\$ to \$n+k\$.  
`⌊⍺*÷2` is the floor of the aqure root of \$k\$.  
`↓` drops this many items from the range. This results in a new range from \$\left\lceil\sqrt{k}\right\rceil\$ to \$n+k\$. These are the values for \$d\$ that satisfy \$d^2>k\$.
`⊢∇¨⊢+⍵-×⍨` is a train applied to this range.  
`×⍨` squares every value. => \$d^2\$  
`⍵-` subtracts each square from \$n+k\$. => \$n+k-d^2\$  
`⊢+` adds the range again. This is needed beacuse we actually call the function with \$n+k\$ and not just \$n\$. => \$n+k-d^2 + d\$  
`⊢` is the right argument, in this this case the potential \$d\$'s.  
`+.∇` is the inner product of the functions `+` and `∇`. First `∇` (recurse) is called on every pair of \$d\$ and \$n+k-d^2 + d\$, then the resulting vector is reduced by addition (`+`).
[Answer]
# [Haskell](https://www.haskell.org/), 53 bytes
A port of my Python answer.
```
(#0)
n#k|n==0=1|w<-n+k=sum[(w-d*d)#d|d<-[1..w],d*d>k]
```
[Try it online!](https://tio.run/##PY0xa8MwGER3/YojbiFJKxEHsgTLS6cOgQ6BDo4HEdmNsPVZyCpOin97VTstnQ7uveMuqm@qto3Gus4HHKtrEG/eUKjZX/XSUfBdKw4dKc1YbQP2e/w6x5ur4CFzvFIA/w9/1664QcLdTSwet3pGU5xoMTNmlaFJ@DLu3YTLAfMmW@ewyqHGA4oUQmC7K6dXeYrLZLNilDQjSbmR6ThknJ4a2X/aYjlwvdarRI8640UqxFA@T0XelDF@n@tWffSRn537AQ "Haskell – Try It Online")
[Answer]
# [Perl 5](https://www.perl.org/) (`-MList::Utils+sum`), 64 bytes
```
sub f{my($n,$k)=@_;sum!$n,map f($n+$k-$_*$_,$_),$k**.5+1..$n+$k}
```
[Try it online!](https://tio.run/##K0gtyjH9/7@4NEkhrTq3UkMlT0clW9PWId66uDRXEcjLTSxQSAMKa6tk66rEa6nE66jEawLVaGnpmWob6umBZWr/FydWgpTFa6blFykAhY3MrLkgYmammtb//@UXlGTm5xX/1/X1ySwusbIKLcnM0QZaARQw1TMwBAA "Perl 5 – Try It Online")
Using @ovs formula
[Answer]
# [Jelly (fork)](https://github.com/DennisMitchell/jelly), 15 bytes
```
ŒṗŒ!€ẎQ½+¥/€Æ²S
```
[Try it online!](https://tio.run/##y0rNyan8///opIc7px@dpPioac3DXX2Bh/ZqH1qqD@Qcbju0Kfj///9mAA "Jelly – Try It Online")
This will work for some inputs on TIO, but will fail for others due to floating point errors. However, my fork has [symbolic math support](https://github.com/cairdcoinheringaahing/jellylanguage/commit/40cc217ec50272370867fc5ea4fbd5c6126f1c11), meaning that it basically never uses floats.
## How it works
This is a brute force attempt. Times out on TIO for \$n \ge 10\$. Uses a similar approach to [Kevin's answer](https://codegolf.stackexchange.com/a/213868/66833), but found independently.
```
ŒṗŒ!€ẎQ½+¥/€Æ²S - Main link. Takes n on the left
Œṗ              - Integer partitions of n
    €           - Over each:
  Œ!            -   Calculate the permutations
     Ẏ          - Merge into a list of lists
      Q         - Deduplicate
           €    - Over each list:
         ¥/     -   Reduce by:
       ½        -     Square root of left
        +       -     Plus right
            Æ²  - Is a square?
              S - Sum
```
]