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.

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

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

Answer 5

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 
               ;0 start with [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?

Answer 6

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!

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!

Answer 8

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]

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.

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.

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

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õ² 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

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

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_ƲẸ¬ʋ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

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αŲ≠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