First sequence with no square differences

Consider the sequence $$\(a_n)\$$ defined in the following way.

• $$\a_0=0\$$
• For all $$\n=1, 2, 3, \dots\$$, define $$\a_n\$$ to be the smallest positive integer such that $$\a_n-a_i\$$ is not a square number, for any $$\0\leq i

In other words, this is the lexicographically first sequence where no two terms differ by a square. It is proven that this sequence is infinite, and it is A030193 in the OEIS. The sequence begins

0, 2, 5, 7, 10, 12, 15, 17, 20, 22, 34, 39, 44, 52, 57, 62, 65, 67, 72, 85, 95, 109, 119, 124, 127, 130, 132, 137, 142, 147, 150, 170, 177, 180, 182, 187, 192, 197, 204, 210, 215, 238, 243, 249, 255, 257, 260, 262, 267,...

Challenge

The challenge is to write a program or function which does one of these:

• Takes a nonnegative integer n and returns or prints the n-th term of this sequence. Either 1-indexed or 0-indexed is acceptable.

• Takes a positive integer n and returns or prints the first n terms of this sequence

• Takes no input and returns or prints all terms of the sequence with an infinite loop or infinite list

Any reasonable form of input and output is allowed.

Example (0-indexed)

Input -> Output
0     -> 0
10    -> 34
40    -> 215


Rules

• Standard loopholes forbidden.

• Code golf: shortest program in bytes for each language wins.

• (remark: many solutions here suffers from floating point error while calculating the square root.) Mar 5, 2021 at 2:53
• @user202729 If I'm not mistaken, our standard rules allow assuming that floating-point is infinitely precise. Mar 5, 2021 at 7:52
• @xigoi Yes, it's not really a problem. Mar 5, 2021 at 12:45
• @xigoi - not completely correct, I think: see this. Mar 5, 2021 at 22:22

Python 3, 67 bytes

Takes no input and prints all terms of the sequence with an infinite loop.

n,*a=0,
while 1:a+=n*(all((n-i)**.5%1for i in a)>0!=print(n)),;n+=1


Try it online!

Ruby, 72625750 47 bytes

0.step{|x|$*<<p(x)if$*.all?{|i|(x-i)**0.5%1>0}}


Try it online!

Prints all terms of the sequence indefinitely.

7 bytes saved by Dingus and further 3 by Sisyphus.

Ruby 2.7+, 45 bytes

0.step{|x|$*<<p(x)if$*.all?{(x-_1)**0.5%1>0}}


Python 3, 101 93 bytes

f=lambda n,l=[],a=0:n and(any((a-b)**.5%1==0for b in l)and f(n,l,a+1)or f(n-1,l+[a],a+1))or l


Try it online!

Inputs a positive integer $$\n\$$ and returns the first $$\n\$$ terms of $$\A030193\$$.

• Why the down vote? I posted first. Mar 3, 2021 at 15:16
• +1 from me to make things even. It's funny when two answers are the same and it has happened to all of us. Mar 3, 2021 at 16:44

Python 3, 1029288 84 bytes

f=lambda n,a=[],x=0:n and f(*[n,n-1,a,a+[x]][all((x-k)**.5%1for k in a)::2],x+1)or a


Try it online!

-4 bytes thanks to movatica

• 84 bytes Mar 5, 2021 at 10:59

Husk, 17 bytes

¡λVoΛoS≠⌊√M≠⁰N);0


Try it online!

Returns an infinite list. The header is used to take 10 elements from it so the result can be displayed.

Explanation

¡λVoΛoS≠⌊√M≠⁰N);0
¡                 iterate on this array, appending results:
λ            )   lambda function (argument → ⁰)
Vo         N    first natural number where
M≠⁰     differences with elements so far
Λo            are all
S≠⌊√        not square?

• Could something in the form ¡ḟN"foo";0 help here?
– user
Mar 4, 2021 at 20:49
• something like this? Try it online! It might be harder to infer. I'll try to get it working. Mar 5, 2021 at 1:50
• Perhaps outer product by summing with the sequence of squares might help?
– user
Mar 5, 2021 at 13:00
• hmm, not sure how I'd use that Mar 5, 2021 at 14:00
• The Jelly answer adds all the previous terms of the sequence to all the squares and makes sure the next term isn't in that sequence, and my Scala answer subtracts all the squares from the number to check, so I was thinking about something like that.
– user
Mar 5, 2021 at 14:06

Retina 0.8.2, 46 bytes

.+
$*¶ +1m^(_*)¶(_+¶)*((\3__|^_))*\1$
$&_ %_  Try it online! Outputs the 0ᵗʰ to nᵗʰ terms. Explanation: The program first matches the 0ᵗʰ and nᵗʰ terms, which initially differ by zero, and increments the nᵗʰ term. On the next pass through the loop, it discovers that the nᵗʰ term differs from the first entry by one, and so increments it again. The difference is now two, so this pair of terms no longer matches. Instead, further passes start incrementing previous terms, until finally the 1ˢᵗ term has been incremented to two. At this point, the 0ᵗʰ term cannot be paired with any other term, so now the 1ˢᵗ term is paired with the nᵗʰ term, as they are both two. The nᵗʰ term thus gets incremented twice to four. At this point however the 0ᵗʰ and nᵗʰ terms can be matched again, so the nᵗʰ term gets incremented to five. Now further passes can start incrementing previous terms, until finally the 2ⁿᵈ term has been incremented to five. Having for now exhausted all matches of the 0ᵗʰ and 1ˢᵗ terms, the 2ⁿᵈ term is now paired with the nᵗʰ term. As before, it gets incremented twice, then further passes increment previous terms, until finally the 3ʳᵈ term has been incremented to seven. Eventually all of the terms get incremented until no two terms differ by a square. (It is however important that only one term gets incremented on each pass, otherwise some terms may get incremented prematurely, being the sum of a square of a term whose value is itself still the sum of a square of a term.) .+$*¶


Generate an array of n+1 terms, all of which start off at zero.

+


Repeat while two terms have a square difference...

1


... update one pair of terms...

m^(_*)¶(_+¶)*((\3__|^_))*\1$ ... match a term, any number of terms, then an term which is a square number plus the initially matched term... $&_


... and add one to that term.

%_


Convert each term to decimal.

At a cost of 2 bytes, using a lookbehind allows all of the terms to be incremented simultaneously, dramatically improving performance:

.+
$*¶ +m$(?<=^\2(¶_+)*¶(_*)((\3__|_$))*) _ %_  Try it online! • That's impressive! Could you explain how matching a square number works? Is that \3 referring to a capturing group from inside that same group? – Leo Mar 4, 2021 at 0:15 • @Leo That's correct! Capture group 3 is quantified. The first time through it hasn't been captured yet, so you're forced to match the alternative of one underscore (at the value's start, or end in lookbehind version). On subsequent times you aren't at the start (end) any more, so you have to capture the previous capture plus two, thus building up the square as a sum of odd numbers. – Neil Mar 4, 2021 at 0:50 JavaScript (ES7), 66 bytes Returns the n-th term, 0-indexed. n=>n&&(k=0,g=a=>a[n]||g(++k*a.every(v=>(k-v)**.5%1)?[...a,k]:a))  Try it online! • Wow! Cannot understand the use of empty template literal at the end, could you explain please ? Mar 4, 2021 at 21:41 • @AZTECCO Same syntax as String.raw . Mar 5, 2021 at 2:50 Jelly, 14 bytes ŻJ²p⁸§Ṭ¬TŻḣðƬṪ  A monadic Link accepting a positive integer $$\N\$$ that yields a list of the first $$\N\$$ terms. Try it online! How? Iterates towards the greedy solution. It would be easier to follow as 0ð... but we can start the Ƭ-loop with $$\N\$$ rather than $$\0\$$ saving those two bytes. ŻJ²p⁸§Ṭ¬TŻḣðƬṪ - Link: N Ƭ - start with a left argument of N, apply repeatedly until no change, collecting the left arguments in a list: ð - dyadic chain - f(L=current left argument, N) Ż - when L is an integer [0..L] (first pass only) when L is a list [0]+L (all other passes) J - range of length -> [1..n+1] (all passes due to ḣ, below) ² - square these -> [1,4,9,...,(n+1)²] ⁸ - L (on the first pass L is N and this is implicitly cast to [1..N]) p - (squares) Cartesian product (L) § - sums -> numbers which are any of L plus any of these squares Ṭ - untruth -> a binary list with ones at those indices ¬ - logical NOT T - truth -> a list of the indices of the truthy entries i.e. a bunch of numbers that aren't in the result of the sums, § Ż - prepend a zero ḣ - head to length (N) Ṫ - tail  As an example of the Ƭ-loop consider $$\N=3\$$: >>> L = 3 ŻJ² -> [1, 4, 9, 16] ŻJ²p⁸ -> [[1, 1], [1, 2], [1, 3], [4, 1], [4, 2], [4, 3], [9, 1], [9, 2], [9, 3], [16, 1], [16, 2], [16, 3]] ŻJ²p⁸§ -> [2, 3, 4, 5, 6, 7, 10, 11, 12, 17, 18, 19] ŻJ²p⁸§Ṭ¬TŻ -> [0, 1, 8, 9, 13, 14, 15, 16] ŻJ²p⁸§Ṭ¬TŻḣ -> [0, 1, 8] >>> L = [0, 1, 8] ŻJ² -> [1, 4, 9, 16] ŻJ²p⁸ -> [[1, 0], [1, 1], [1, 8], [4, 0], [4, 1], [4, 8], [9, 0], [9, 1], [9, 8], [16, 0], [16, 1], [16, 8]] ŻJ²p⁸§ -> [1, 2, 9, 4, 5, 12, 9, 10, 17, 16, 17, 24] ŻJ²p⁸§Ṭ¬TŻ -> [0, 3, 6, 7, 8, 11, 13, 14, 15, 18, 19, 20, 21, 22, 23] ŻJ²p⁸§Ṭ¬TŻḣ -> [0, 3, 6] >>> L = [0, 3, 6] ŻJ² -> [1, 4, 9, 16] ŻJ²p⁸ -> [[1, 0], [1, 3], [1, 6], [4, 0], [4, 3], [4, 6], [9, 0], [9, 3], [9, 6], [16, 0], [16, 3], [16, 6]] ŻJ²p⁸§ -> [1, 4, 7, 4, 7, 10, 9, 12, 15, 16, 19, 22] ŻJ²p⁸§Ṭ¬TŻ -> [0, 2, 3, 5, 6, 8, 11, 13, 14, 17, 18, 20, 21] ŻJ²p⁸§Ṭ¬TŻḣ -> [0, 2, 3] >>> L = [0, 2, 3] ŻJ² -> [1, 4, 9, 16] ŻJ²p⁸ -> [[1, 0], [1, 2], [1, 3], [4, 0], [4, 2], [4, 3], [9, 0], [9, 2], [9, 3], [16, 0], [16, 2], [16, 3]] ŻJ²p⁸§ -> [1, 3, 4, 4, 6, 7, 9, 11, 12, 16, 18, 19] ŻJ²p⁸§Ṭ¬TŻ -> [0, 2, 5, 8, 10, 13, 14, 15, 17] ŻJ²p⁸§Ṭ¬TŻḣ -> [0, 2, 5] >>> L = [0, 2, 5] ŻJ² -> [1, 4, 9, 16] ŻJ²p⁸ -> [[1, 0], [1, 2], [1, 5], [4, 0], [4, 2], [4, 5], [9, 0], [9, 2], [9, 5], [16, 0], [16, 2], [16, 5]] ŻJ²p⁸§ -> [1, 3, 6, 4, 6, 9, 9, 11, 14, 16, 18, 21] ŻJ²p⁸§Ṭ¬TŻ -> [0, 2, 5, 7, 8, 10, 12, 13, 15, 17, 19, 20] ŻJ²p⁸§Ṭ¬TŻḣ -> [0, 2, 5] >>> [0, 2, 5] >>> seen previously, so stop the Ƭ-loop and yield: [3, [0, 1, 8], [0, 3, 6], [0, 2, 3], [0, 2, 5]] Ṫ -> [0, 2, 5]  Haskell, 56 bytes n!l|or[elem(n-y*y)l|y<-[0..n]]=(n+1)!l|m<-n:l=n:n!m 0![]  Try it online! 0![] is an infinite list of the results. This draws some inspiration from AZTECCO's answer. • What the heck! Great! It seems so simple now lol Mar 4, 2021 at 14:14 R, 857667 63 bytes Edit: -9 bytes thanks to Giuseppe, and then -4 bytes thanks to Kirill L. s=0;repeat{s=c(F,s);show(+F);while(any((0:F)^2%in%(F-s)))F=F+1}  Try it online! Outputs the infinite sequence. • Would this work? Seems like you don't need the outer... Mar 3, 2021 at 19:11 • @Giuseppe - I'm sure I tried something-or-other and concluded (wrongly) that I needed the outer... Thanks! Mar 3, 2021 at 19:56 • I think, you can swap 0:s for 0:F and avoid assigning F=2. It would no longer work with your while construct, but can be rewritten with repeat for 63 bytes Mar 4, 2021 at 18:01 • @KirillL. - That's really neat how it solves the F=2 problem! Thanks! (And I always seem to forget about repeat because I never use it in "real" programming...) Mar 4, 2021 at 20:11 K (ngn/k), 31 29 bytes {*|x{x,{y+|/~1!%y-x}[x]/0}/0}  Try it online! Returns the n-th item of the series (0-indexed). If it's acceptable to return the first n+1 terms of the sequence, the leading *| can be dropped to save two bytes. • {*|...} return only the last item of the generated sequence • x{...}/0 run a fold-do loop, for x iterations seeded with 0 • {...}[x]/0 run a fold-converge loop, fixing x (the generated sequence so far), seeded with 0. this will stop when the next value in the sequence has been identified • %y-x take the square root of the differences between the current loop value and each value in the generated sequence so far • ~1! check if any difference is a square number (i.e. if it has a remainder of zero after being mod'd by 1) • y+|/ increment the current loop value if it is not the next term in the sequence • {x,...} append the next value in the sequence PowerShell, 76 75 69 64 bytes Takes no input, outputs the infinite series (up to the maximum for a 64-bit signed integer) for(){($a+=,+$n*!($a|?{!([Math]::Sqrt($n-$_)%1)}).Count)-eq$n++}  Try it online! Wolfram Language (Mathematica), 55 bytes returns the first n terms Nest[#~Join~{While[Or@@AtomQ/@√(++k-#)];k}&,{k=0},#]&  Try it online! -11 bytes thanks to @att • 55 bytes – att Mar 3, 2021 at 18:27 Wolfram Language (Mathematica), 51 bytes g@n_:=g@m_/;AtomQ@√(m-n)=Print@n i=0 g@i++~Do~∞  Try it online! Outputs the list indefinitely. Japt, 27 23 22 bytes @A{ZmaA fAõ² l}fXÄ}h0ô  Try it online! Returns the first n numbers in the sequence. If you replace h with g it instead returns the nth number in the sequence (0-indexed). Improvements: • Used "difference is in list of squares" instead of "square root of difference is an integer" to save 4 bytes, inspired by Jonathan Allan's Jelly answer • Used 0ô to initialize the array as suggested by AZTECCO Explanation: @A{ZmaA fAõ² l}fXÄ}h0ô 0ô # Starting with [0] @ }h # Add elements to the array until the length is n: A{ }fXÄ # Find the next integer A that returns 0: Zm # For each element already in the array: aA # Get the absolute difference between it and A f # Remove any elements that are also in: Aõ² # All squares up to A^2 l # Count how many elements are left  • You can replace h[0] with h0ô to save 1 Mar 4, 2021 at 14:27 JavaScript, 66 bytes _=>{a=[];for(i=0;;i++)a.every(x=>(i-x)**.5%1)&&a.push(i);return a}  Adds the terms of the sequence to an array with an infinite loop. Try it online! JavaScript (V8), 77 76 bytes n=>{a=[];for(i=0;a.length<n;i++)a.every(x=>(i-x)**.5%1)&&a.push(i);print(a)}  Prints the first n terms of the sequence. Try it online! Explanation n=>{ a=[];//array of terms in the sequence for(i=0;a.length<n;i++) //loop until array length is n a.every(x=>(i-x)**.5%1) //check if square root of delta with each previous number in sequence is not an integer &&a.push(i);//then add to array print(a)//output array (return works too) }  • I wanted to shorten it by making a version that prints indefinetly (removing the limit test) but it actually end up having the same length, maybe it can be a hint to make it shorter? Mar 3, 2021 at 16:39 • @Kaddath The link doesn't seem to work. Mar 3, 2021 at 16:43 • Yes I see that, here is the code directly: n=>{a=[j=0];for(i=1;;i++)a.every(x=>(i-x)**.5%1)&&a.push(i)&&!print(a[j++]);} (too late to edit my comment). It was just a quick try I think it can be improved Mar 3, 2021 at 16:47 • @Kaddath Thanks for the idea. I've added to my answer. Mar 3, 2021 at 17:08 J, 35 bytes 0&(],]>:@]^:(1 e.(=<.)@%:@-)^:_[)0:  Try it online! Given n, returns the first n+1 terms. Scala, 109 bytes Stream.iterate(0::Nil)(s=>Stream.from(s(0)).find(x=> !s.exists(Set(0 to x:_*)map(a=>x-a*a))).get::s)map(_(0))  Try it in Scastie! An infinite Stream. First n elements, 100 bytes Stream.iterate(0::Nil)(s=>Stream.from(s(0)).find(x=> !s.exists(Set(0 to x:_*)map(a=>x-a*a))).get::s)  This is the exact same code, just without the map(_(0)) part at the end. Given an n, it gives the first n elements of the sequence, but in reverse. Another 100 byte solution 1.to(_)./:(0::Nil)((s,_)=>Stream.from(s(0)).find(x=> !s.exists(Set(0 to x:_*)map(a=>x-a*a))).get::s)  Try it in Scastie Explanation: Stream.iterate //Build an infinite Stream by repeatedly applying a function to (0::Nil) //A List containing only a 0 (s=> //The previous elements (in reverse) Stream.from(s(0)) //Make a Stream starting from the last element .find(x=> //Find a number with no square difference !s.exists( //Make sure none of the previous elements are in this Set: Set(0 to x:_*) //Start with a set of integers from 0 to x map(a=>x-a*a) //Subtract square from x (to get all elements with squared differences) ) ).get //Unwrap the Option (as the sequence is infinite) ::s //Prepend to s, the sequence )map(_(0)) //Get the first (or rather, last) element of each partial sequence  Jelly, 15 14 bytes ;0_Æ²Ẹ¬ʋ1#$\$¡Ṗ


Try it online!

Prints the first n terms.

If we allow outputting the first n+1 items (as some answers are doing), then it's 13 bytes (without the last character).

-1 byte thanks to Jonathan Allan

• Zero is the implicit left argument of a Link, so you can get rid of the leading 0 :) Mar 3, 2021 at 23:22
• @JonathanAllan Oh, I forgot that if you take input from STDIN, it won't be grven to the link, but will be given to quicks that are missing a nilad. Thanks! Mar 4, 2021 at 7:23

Haskell, 95 89 bytes

n!l|and[y*y/=n-x|x<-l,y<-[0..n-x]]=n:l|m<-n+1=m!l
f n=iterate(\l@(h:t)->(h+1)!l)[0]!!n!!0


Try it online!

• saved 6 thanks to @Wheat Wizard !

• uses this tip Don't waste the "otherwise" guard

• returns nth term 0-indexed

• f(n) - iterates (!) n times, starting with [0] and prepends next term. then takes the element in front because list is reversed.

• (!) tries next number at beginning of list: if it satisfy condition returns it prepended to list else try the next

APL (Dyalog Unicode), 34 bytes

{∇⍵,⎕←⊃(g~⊢)∊⍵∘.+2*⍨(g←⍳2+⌈/)⍵}⎕←0


Try it online!

With a train (and a small dfn), 41 bytes

(⊢,(({⎕←⊃⍵}g∘∊~⊢)∘.+∘(2*⍨g←⍳2+⌈/)⍨))⍣≡⎕←0


Try it online!

C (gcc), 99 bytes

m,i,k;f(n,l){l*=!!m++;for(i=1;i<m;k%=m,i+=!k)k+=(&l)[i*8]+k*k-l||(l+=i=k=1);!n?m=0,n=l:f(n-1,l+1);}


Try it online!

Takes n as input and returns the n-th number in the sequence (0-indexed)

C (gcc), 78 bytes

shorter solution, extremely slow for n > 8

Edit: -2 Bytes thanks to ceilingcat

f(n,i,k,r){r=n?f(n-1):0;for(i=k=0;k<n;i>n?i=!++k:++i)k=f(k)+i*i-r?k:!++r;n=r;}


Try it online!

Raku, 36 bytes

0,{first (*-@_.all).sqrt%1,^∞}...*


Try it online!

This is an expression for a lazy, infinite sequence of the required values.

05AB1E, 13 bytes

0λλU∞.ΔXαÅ²≠P


Outputs the infinite sequence.

Try it online.

Should have been 11 bytes by removing λU and changing X to λ (0λ∞.ΔλαÅ²≠P), but unfortunately the recursive environment builtin still has some issues here and there, and apparently trying to retrieve the recursive-list λ inside a nested loop (.Δ in this case) doesn't work.

Outputting the first $$\n\$$ or $$\n^{th}\$$ value would be 1 byte longer than the infinite list:
try the first $$\n\$$ online or try the 0-based $$\n^{th}\$$ online.

Explanation:

 λ              # Start a recursive environment,
# to output the infinite sequence implicitly as result afterwards,
0               # starting a(0)=0,
# and where every following a(n) is calculated as follows:
λ            #  Push a list of the previous results of a(0)..a(n-1)
U           #  Pop and store this list in variable X
∞.Δ        #  Find the first positive integer [1,2,3,...] which is truthy for:
X       #   Push list X
α      #   Get for each the absolute difference with the current integer
Å²    #   Check for each whether it's a square number
≠   #   Invert each boolean, so we check they're NOT a square number
P  #   And check if this is truthy for all of them
`