First sequence with no square differences

Question

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

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.

• user202729: (remark: many solutions here suffers from floating point error while calculating the square root.)
• Adamátor: @user202729 If I'm not mistaken, our standard rules allow assuming that floating-point is infinitely precise.
• user202729: @xigoi Yes, it's not really a problem.
• Dominic van Essen: @xigoi - not completely correct, I think: see this.

Answer 1

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!

Answer 2

Ruby, (削除) 72 (削除ここまで) (削除) 62 (削除ここまで) (削除) 57 (削除ここまで) (削除) 50 (削除ここまで) 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}}

Answer 3

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

• Noodle9: Why the down vote? I posted first.
• ZaMoC: +1 from me to make things even. It's funny when two answers are the same and it has happened to all of us.

Answer 4

Python 3, (削除) 102 (削除ここまで) (削除) 92 (削除ここまで) (削除) 88 (削除ここまで) 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

• movatica: 84 bytes

Answer 5

Husk, 17 bytes

¡λVoΛoS≠⌊√M≠0N);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≠0N);0 
 ;0 start with [0]
¡ iterate on this array, appending results:
 λ ) lambda function (argument → 0)
 Vo N first natural number where
 M≠0 differences with elements so far
 Λo are all
 S≠⌊√ not square?

• user: Could something in the form ¡`ḟN"foo";0 help here?
• Razetime: something like this? Try it online! It might be harder to infer. I'll try to get it working.
• user: Perhaps outer product by summing with the sequence of squares might help?
• Razetime: hmm, not sure how I'd use that
• user: 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.

Answer 6

Retina 0.8.2, 46 bytes

.+
$*¶
+1m`^(_*)¶(_+¶)*((3円__|^_))*1円$
$&_
%`_

Try it online! Outputs the 0th to nth terms. Explanation: The program first matches the 0th and nth terms, which initially differ by zero, and increments the nth term. On the next pass through the loop, it discovers that the nth 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 1st term has been incremented to two. At this point, the 0th term cannot be paired with any other term, so now the 1st term is paired with the nth term, as they are both two. The nth term thus gets incremented twice to four. At this point however the 0th and nth terms can be matched again, so the nth term gets incremented to five. Now further passes can start incrementing previous terms, until finally the 2nd term has been incremented to five. Having for now exhausted all matches of the 0th and 1st terms, the 2nd term is now paired with the nth term. As before, it gets incremented twice, then further passes increment previous terms, until finally the 3rd 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!

• Leo: 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?
• Neil: @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.

Answer 7

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!

• AZTECCO: Wow! Cannot understand the use of empty template literal at the end, could you explain please ?
• user202729: @AZTECCO Same syntax as String.raw`` .

Answer 8

Jelly, 14 bytes

ŻJ2p8§Ṭ¬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.

ŻJ2p8§Ṭ¬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)
 2 - square these -> [1,4,9,...,(n+1)2]
 8 - 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
ŻJ2 -> [1, 4, 9, 16]
ŻJ2p8 -> [[1, 1], [1, 2], [1, 3], [4, 1], [4, 2], [4, 3], [9, 1], [9, 2], [9, 3], [16, 1], [16, 2], [16, 3]]
ŻJ2p8§ -> [2, 3, 4, 5, 6, 7, 10, 11, 12, 17, 18, 19]
ŻJ2p8§Ṭ¬TŻ -> [0, 1, 8, 9, 13, 14, 15, 16]
ŻJ2p8§Ṭ¬TŻḣ -> [0, 1, 8]
>>> L = [0, 1, 8]
ŻJ2 -> [1, 4, 9, 16]
ŻJ2p8 -> [[1, 0], [1, 1], [1, 8], [4, 0], [4, 1], [4, 8], [9, 0], [9, 1], [9, 8], [16, 0], [16, 1], [16, 8]]
ŻJ2p8§ -> [1, 2, 9, 4, 5, 12, 9, 10, 17, 16, 17, 24]
ŻJ2p8§Ṭ¬TŻ -> [0, 3, 6, 7, 8, 11, 13, 14, 15, 18, 19, 20, 21, 22, 23]
ŻJ2p8§Ṭ¬TŻḣ -> [0, 3, 6]
>>> L = [0, 3, 6]
ŻJ2 -> [1, 4, 9, 16]
ŻJ2p8 -> [[1, 0], [1, 3], [1, 6], [4, 0], [4, 3], [4, 6], [9, 0], [9, 3], [9, 6], [16, 0], [16, 3], [16, 6]]
ŻJ2p8§ -> [1, 4, 7, 4, 7, 10, 9, 12, 15, 16, 19, 22]
ŻJ2p8§Ṭ¬TŻ -> [0, 2, 3, 5, 6, 8, 11, 13, 14, 17, 18, 20, 21]
ŻJ2p8§Ṭ¬TŻḣ -> [0, 2, 3]
>>> L = [0, 2, 3]
ŻJ2 -> [1, 4, 9, 16]
ŻJ2p8 -> [[1, 0], [1, 2], [1, 3], [4, 0], [4, 2], [4, 3], [9, 0], [9, 2], [9, 3], [16, 0], [16, 2], [16, 3]]
ŻJ2p8§ -> [1, 3, 4, 4, 6, 7, 9, 11, 12, 16, 18, 19]
ŻJ2p8§Ṭ¬TŻ -> [0, 2, 5, 8, 10, 13, 14, 15, 17]
ŻJ2p8§Ṭ¬TŻḣ -> [0, 2, 5]
>>> L = [0, 2, 5]
ŻJ2 -> [1, 4, 9, 16]
ŻJ2p8 -> [[1, 0], [1, 2], [1, 5], [4, 0], [4, 2], [4, 5], [9, 0], [9, 2], [9, 5], [16, 0], [16, 2], [16, 5]]
ŻJ2p8§ -> [1, 3, 6, 4, 6, 9, 9, 11, 14, 16, 18, 21]
ŻJ2p8§Ṭ¬TŻ -> [0, 2, 5, 7, 8, 10, 12, 13, 15, 17, 19, 20]
ŻJ2p8§Ṭ¬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]

Answer 9

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.

• AZTECCO: What the heck! Great! It seems so simple now lol

Answer 10

R, (削除) 85 (削除ここまで) (削除) 76 (削除ここまで) (削除) 67 (削除ここまで) 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.

• Giuseppe: Would this work? Seems like you don't need the outer...
• Dominic van Essen: @Giuseppe - I'm sure I tried something-or-other and concluded (wrongly) that I needed the outer... Thanks!
• Kirill L.: 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
• Dominic van Essen: @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...)

Answer 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

Answer 12

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!

Answer 13

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

• att: 55 bytes

Answer 14

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.

Answer 15

Japt, (削除) 27 23 (削除ここまで) 22 bytes

@A{ZmaA fAõ2 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õ2 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õ2 # All squares up to A^2
 l # Count how many elements are left

• AZTECCO: You can replace h[0] with h0ô to save 1

Answer 16

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)
}

• Kaddath: 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?
• Unmitigated: @Kaddath The link doesn't seem to work.
• Kaddath: 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
• Unmitigated: @Kaddath Thanks for the idea. I've added to my answer.

Answer 17

J, 35 bytes

0&(],]>:@]^:(1 e.(=<.)@%:@-)^:_[)0:

Try it online!

Given n, returns the first n+1 terms.

Answer 18

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

Answer 19

Jelly, (削除) 15 (削除ここまで) 14 bytes

;0_Æ2Ẹ¬ʋ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

• Jonathan Allan: Zero is the implicit left argument of a Link, so you can get rid of the leading 0 :)
• Adamátor: @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!

Answer 20

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

Answer 21

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!

Answer 22

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!

Answer 23

Raku, 36 bytes

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

Try it online!

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

Answer 24

05AB1E, 13 bytes

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

Outputs the infinite sequence.

Try it online.

Should have been 11 bytes by removing λU and changing X to λ (0λ∞.ΔλαÅ2≠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
 Å2 # 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