17
\$\begingroup\$

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

\$\endgroup\$
8
  • 1
    \$\begingroup\$ :'-( \$\endgroup\$
    – Mr. Xcoder
    Oct 12 '17 at 13:57
  • 1
    \$\begingroup\$ @Mr.Xcoder That just makes it interesting! \$\endgroup\$
    – orlp
    Oct 12 '17 at 13:58
  • \$\begingroup\$ @Mr.Xcoder Yeah I agree it's so bad you can't just copy-paste the formula... \$\endgroup\$ Oct 12 '17 at 14:03
  • 2
    \$\begingroup\$ @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'. \$\endgroup\$
    – orlp
    Oct 12 '17 at 14:12
  • 1
    \$\begingroup\$ Are errors caused by floating point inaccuracies acceptable for very large inputs? \$\endgroup\$
    – Zgarb
    Oct 12 '17 at 14:12
4
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ 92 bytes -> while n in s or(t+n)**.5%1>0 -> while(n in s)+(t+n)**.5%1 \$\endgroup\$
    – Mr. Xcoder
    Oct 12 '17 at 14:28
  • \$\begingroup\$ 87 bytes \$\endgroup\$
    – ovs
    Oct 12 '17 at 14:30
  • \$\begingroup\$ @ovs clever one \$\endgroup\$ Oct 12 '17 at 16:43
3
\$\begingroup\$

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)
\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ 99 bytes. \$\endgroup\$ Oct 12 '17 at 14:20
  • \$\begingroup\$ @JonathanFrech Thanks :) \$\endgroup\$
    – TFeld
    Oct 12 '17 at 14:20
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.