Sequence of integer square roots

Question

Let's define a sequence of integer square roots. First, a(1) = 1. Then, a(n) is the smallest positive integer not seen before such that

sqrt(a(n) + sqrt(a(n-1) + sqrt(... + sqrt(a(1)))))

is an integer. Some examples:

a(2) is 3 because it's the smallest integer such that sqrt(a(2) + sqrt(a(1))) = sqrt(a(2) + 1) is integer, and 3 hasn't occured in the sequence before.

a(3) is 2 because it's the smallest integer such that sqrt(a(3) + sqrt(a(2) + sqrt(a(1)))) = sqrt(a(3) + 2) is integer, and 2 hasn't occured in the sequence before.

a(4) is 7 because sqrt(a(4) + 2) is integer. We couldn't have a(4) = 2 because 2 already occured in our sequence.

Write a program or function that given a parameter n returns a sequence of numbers a(1) to a(n).

The sequence starts 1,3,2,7,6,13,5, ....

^{Source of this sequence is from this Math.SE question.}

---

A plot of the first 1000 elements in the sequence:

plot

• Mr. Xcoder: :'-(
• orlp: @Mr.Xcoder That just makes it interesting!
• Erik the Outgolfer: @Mr.Xcoder Yeah I agree it's so bad you can't just copy-paste the formula...
• orlp: @EriktheOutgolfer No. When you get n as input you should return or print a list of a(1) to a(n). In other words, the first n numbers in the sequence. There is no 'indexing'.
• Zgarb: Are errors caused by floating point inaccuracies acceptable for very large inputs?

Answer 1

Python 2, 80 bytes

s=[]
exec'x=q=1\nwhile(x in s)+q%1:x+=1;q=(v+x)**.5\nv=q;s+=x,;'*input()
print s

Try it online!

Answer 2

Haskell, (削除) 103 (削除ここまで) 87 bytes

Horribly inefficient, but does not rely on floating point arithmetic. Here a(x) = sqrt(f(x)+a(x-1)) is a helper sequence, that simplifies the computation.

a 0=0
a x=[k|k<-[1..],m<-[k^2-a(x-1)],m>0,notElem m$f<$>[1..x-1]]!!0
f x=(a x)^2-a(x-1)

Try it online!

Answer 3

Python 2, 87 bytes

t,=s=1,
for n in~-input()*s:
 while(n in s)+(t+n)**.5%1:n+=1
 s+=n,;t=(t+n)**.5
print s

Try it online!

-3 thanks to Mr. Xcoder.
-5 thanks to ovs.

• Mr. Xcoder: 92 bytes -> while n in s or(t+n)**.5%1>0 -> while(n in s)+(t+n)**.5%1
• ovs: 87 bytes
• Erik the Outgolfer: @ovs clever one

Answer 4

MATL, (削除) 30 (削除ここまで) 27 bytes

lXHiq:"`@ymH@+X^1\+}8MXHx@h

Try it online! Or see a graphical display (takes a while; times out for inputs exceeding approximately 60).

Explanation

l % Push 1. This is the array that holds the sequence, initialized to
 % a single term. Will be extended with subsequent terms
XH % Copy into clipboard H, which holds the latest result of the 
 % "accumulated" square root
iq:" % Input n. Do the following n-1 times
 ` % Do...while
 @ % Push interaton index k, starting at 1. This is the candidate
 % to being the next term of the sequence
 y % Push copy of array of terms found so far
 m % Ismbmer? True if k is in the array
 H % Push accumulated root
 @+ % Add k
 X^ % Square root
 1\ % Modulo 1. This gives 0 if k gives an integer square root
 + % Add. Gives nonzero if k is in the array or doesn't give an
 % integer square root; that is, if k is invalid.
 % The body of the do...while loop ends here. If the top of the
 % stack is nonzero a new iteration will be run. If it is zero that
 % means that the current k is a new term of the sequence
 } % Finally: this is executed after the last iteration, right before
 % the loop is exited
 8M % Push latest result of the square root
 XH % Copy in clipboard K
 x % Delete
 @ % Push current k
 h % Append to the array
 % End do...while (implicit)
 % Display (implicit)

Answer 5

Mathematica, 104 bytes

(s=f={i=1};Do[t=1;While[!IntegerQ[d=Sqrt[t+s[[i]]]]||!f~FreeQ~t,t++];f~(A=AppendTo)~t;s~A~d;i++,#-1];f)& 

Try it online!

The sequence of the square roots is also very interesting...
and outputs a similar pattern

1,2,2,3,3,4,3,5,3,6,4,4,5,4,6,5,5,6,6,7,4,7,5,7,6,8,4,8,5,8,6,9,5,9,6,10,5,10,6,11,5,11,6,12,6,13,6,14,7,7,8,7,9,7,10,7,11,7,12,7,13,7,14,8,8,9,8,10...

enter image description here

also here are the differences of the main sequence

enter image description here

Answer 6

Python 2, (削除) 117 (削除ここまで) (削除) 115 (削除ここまで) (削除) 112 (削除ここまで) (削除) 102 (削除ここまで) (削除) 99 (削除ここまで) 87 bytes

t,=r=1,;exec"x=1\nwhile(t+x)**.5%1or x in r:x+=1\nr+=x,;t=(t+x)**.5;"*~-input();print r

Try it online!

Used the t=(t+x)**.5 logic from Erik's answer

• Jonathan Frech: 99 bytes.
• TFeld: @JonathanFrech Thanks :)

Answer 7

JavaScript (ES7), (削除) 89 (削除ここまで) (削除) 82 (削除ここまで) (削除) 77 (削除ここまで) 76 bytes

i=>(g=k=>(s=(++n+k)**.5)%1||u[n]?g(k):i--?[u[n]=n,...g(s,n=0)]:[])(n=0,u=[])

Demo

let f =
i=>(g=k=>(s=(++n+k)**.5)%1||u[n]?g(k):i--?[u[n]=n,...g(s,n=0)]:[])(n=0,u=[])
console.log(JSON.stringify(f(10)))

Formatted and commented

i => ( // given i = number of terms to compute
 u = [], // u = array of encountered values
 g = p => // g = recursive function taking p = previous square root
 (s = (++n + p) ** .5) % 1 // increment n; if n + p is not a perfect square,
 || u[n] ? // or n was already used:
 g(p) // do a recursive call with p unchanged
 : // else:
 i-- ? // if there are other terms to compute:
 [u[n] = n, ...g(s, n = 0)] // append n, set u[n] and call g() with p = s, n = 0
 : // else:
 [] // stop recursion
 )(n = 0) // initial call to g() with n = p = 0

Answer 8

R, (削除) 138 (削除ここまで) (削除) 105 (削除ここまで) 99 bytes

function(n){for(i in 1:n){j=1
while(Reduce(function(x,y)(y+x)^.5,g<-c(T,j))%%1|j%in%T)j=j+1
T=g}
T}

Try it online!

-33 bytes using Tfeld's clever sqrt()%%1 trick in the while loop

-6 bytes using T instead of F

original answer, 138 bytes:

function(n,l={}){g=function(L)Reduce(function(x,y)(y+x)^.5,L,0)
for(i in 1:n){T=1
while(g(c(l,T))!=g(c(l,T))%/%1|T%in%l)T=T+1
l=c(l,T)}
l}

Try it online!

Answer 9

Husk, 21 bytes

!¡oḟȯΛ±sFo√+Som:`-N;1

Try it online!

How?

!¡oḟȯΛ±sFo√+Som:`-N;1 Function that generates a list of prefixes of the sequence and indexes into it
 ;1 The literal list [1]
 ¡ Iterate the following function, collecting values in a list
 oḟȯΛ±sFo√+Som:`-N This function takes a prefix of the sequence, l, and returns the next prefix.
 `-N Get all the natural numbers that are not in l.
 Som: Append l in front each of these numbers, generates all possible prefixes.
 ȯΛ±sFo√+ This predicate tests if sqrt(a(n) + sqrt(a(n-1) + sqrt(... + sqrt(a(1))))) is an integer.
 F Fold from the left
 o√+ the composition of square root and plus
 s Convert to string
 ȯΛ± Are all the characters digits, (no '.')
 oḟ Find the first list in the list of possible prefixes that satisfies the above predicate
! Index into the list