"Early bird" squares

Question

Definition

If you take the sequence of positive integer squares, and concatenate them into a string of digits (i.e. 149162536496481100...), an "early bird" square is one that can be found in this string ahead of its natural position.

For example, 7² (the number 49), can be found at an offset of 2 in the string, although the natural position is at offset 10. Thus 7 is the first "early bird" square.

Note that for it to be considered an "early bird" square, all the digits in the square must occur before the start of the natural position. A match that partially overlaps the natural position does not count.

a(n) is the nth positive integer k such that k² is an "early bird" square.

Task

Given a positive integer n, output a(n).

You can use 1-based or 0-based indexing, but if you use 0-based indexing, please say so in your answer.

You solution should be able to handle at least as high as a(53) (or if you're using 0-based indexing, a(52)).

Testcases

n     a(n)
1     7
2     8
3     21
4     25
5     46
6     97
7     129
8     161
9     196
10    221
...
13    277
...
50    30015
51    35000
52    39250
53    46111

References

• OEIS A181585

Answer 1

JavaScript (ES6), 51 49 45 bytes

1-indexed.

f=(n,s=k='')=>n?f(n-!!s.match(++k*k),s+k*k):k

Demo

f=(n,s=k='')=>n?f(n-!!s.match(++k*k),s+k*k):k

for(n = 1; n <= 20; n++) {
  console.log('a(' + n + ') = ' + f(n))
}

Formatted and commented

f = (                         // f = recursive function taking:
  n,                          //   n = input
  s = k = ''                  //   s = string of concatenated squares, k = counter
) =>                          //
  n ?                         // if we haven't reached the n-th term yet:
    f(                        //   do a recursive call with:
      n - !!s.match(++k * k), //     n decremented if k² is an early bird square
      s + k * k               //     s updated
    )                         //   end of recursive call
  :                           // else:
    k                         //   return k

Non-recursive version, 53 bytes

This one does not depend on your engine stack size.

n=>{for(k=s='';n-=!!(s+=k*k).match(++k*k););return k}

Try it online!

Answer 2

Pyth, 12 bytes

e.f/jk^R2Z`*

Try it here!

How it works

e.f/jk^R2Z`* ~ Full program. Let Q be our input.

 .f          ~ First Q positive integers with truthy results. Uses the variable Z.
      ^R2Z   ~ Square each integer in the range [0, Z).
    jk       ~ Concatenate into a single string.
   /         ~ Count the occurrences of...
          `* ~ The string representation of Z squared.
               Yields 0 if falsy and ≥ 1 if truthy.
e            ~ Get the last element (Qth truthy integer). Output implicitly.

Answer 3

05AB1E, 10 9 bytes

Saved 1 byte thanks to Adnan.

µNL<nJNnå

Try it online!

Explanation

µ           # loop until counter equals the input
 NL         # push the range [1 ... iteration_no]
   <        # decrement each
    n       # square each
     J      # join to string
      Nnå   # is iteration_no in the string?
            # if true, increase counter

Answer 4

Perl 5, 34 bytes

33 bytes code + 1 for -p.

$s.=$\*$\while$_-=$s=~(++$\*$\)}{

Try it online!

Answer 5

APL (Dyalog), 53 42 bytes

{{0<+/(⍕×⍨⍵+1)⍷' '~⍨⍕×⍨⍳⍵:⍵+1⋄∇⍵+1}⍣⍵⊢0}

Try it online!

How?

⍷ - find occurrences of

⍕×⍨⍵+1 - stringified square of x+1 in the

⍕×⍨⍳⍵ - stringified range of squares x

' '~⍨ - without spaces

+/ - sum

0< - if the sum is positive (occurrences exist), then it returns x+1, otherwise,

∇⍵+1 - recurse with x+1.

⍣⍵ - apply n times.

Answer 6

Haskell, 73 bytes

import Data.List
([n|n<-[7..],isInfixOf(g n)$g=<<[1..n-1]]!!)
g=show.(^2)

Try it online! Zero-indexed.

Explanation

Auxiliaries:

import Data.List -- import needed for isInfixOf
g=show.(^2)      -- function short cut to square an int and get the string representation

Main function:

(                                 !!) -- Index into the infinite sequence
 [n|n<-[7..],                    ]    -- of all numbers n greater equal 7
      isInfixOf(g n)$                 -- whose square appears in the string
                     g=<<[1..n-1]     -- of all squares from 1 up to n-1 concatenated.

Answer 7

Jelly, 13 11 bytes

R²DµṪẇF
Ç#Ṫ

Try it online!

Alternatively this is a 10 bytes solution that prints n first values of the sequence: Try it online!

Answer 8

Python 2, 62 61 bytes

n=input();i=0;s=''
while n:i+=1;n-=`i*i`in s;s+=`i*i`
print i

Try it online!

Answer 9

Jelly, 11 bytes

Ḷ²DFɓ²ẇ
Ç#Ṫ

Try it online!

An alternative to user202729's solution.

How it works

C#Ṫ ~ Main Link.

Ç#  ~ First N positive integers with truthy results.
  Ṫ ~ Tail. Take the last one.

-----------------------------------------------------------

Ḷ²DFɓ²ẇ ~ Helper link. This is the filtering condition.

Ḷ       ~ Lowered range. Yields {x | x ∊ Z and x ∊ [0, N)}.
 ²      ~ Square each.
  D     ~ Convert each to decimal (this gets the list of digits).
   F    ~ Flatten.
    ɓ   ~ Starts a new monadic chain with swapped arguments.
     ²  ~ N²; Yields N squared.
      ẇ ~ Is ^ sublist of ^^^?
 

Answer 10

Alice, 32 bytes

/
\io/&wd.*\@! d ? ~ ? F $ /WKdt

Try it online!

The wasteful layout of that stretch of Ordinal mode is really bugging me, but everything I try to save some bytes there comes out longer...

Explanation

/
\io/...@...

Just the usual decimal I/O framework, with the o and @ in slightly unusual positions. The meat of the program is this:

&w    Push the current IP address to the return address stack n times.
      This gives us an easy way to write a loop which repeats until we
      explicitly decrement the loop counter n times.

  d     Push the stack depth, which acts as our running iterator through
        the natural numbers.
  .*    Square it.
  \     Switch to Ordinal mode.
  !     Store the square (as a string) on the tape.
  d     Push the concatenation of the entire stack (i.e. of all squares before
        the current one).
  ?~    Retrieve a copy of the current square and put it underneath.
  ?     Retrieve another copy.
  F     Find. If the current square is a substring of the previous squares,
        this results in the current square. Otherwise, this gives an empty
        string.
  $     If the previous string was empty (not an early bird) skip the next
        command.
  /     Switch back to Cardinal. This is NOT a command.
  W     Discard one address from the return address stack, decrementing our
        main loop counter if we've encountered an early bird.
K     Jump back to the beginning of the loop if any copies of the return
      address are left. Otherwise do nothing and exit the loop.

dt    Push the stack depth and decrement it, to get the final result.

Answer 11

Husk, 13 bytes

!f§€oṁ₁ŀ₁N
d□

Try it online!

Explanation

The second line is a helper function which gives us the decimal digits of a number's square:

 □    Square.
d     Base-10 digits.

We can invoke this function on the main program using ₁.

!f§€oṁ₁ŀ₁N
 f§      N    Filter the list of natural numbers by the following fork g(n).
       ŀ        Get [0, 1, ... n-1]
     ṁ₁         Get the decimal digits of each value's square and concatenate
                them into one list. (A)
        ₁       And get the decimal digits of n² itself. (B)
    €           Check whether (A) contains (B) as a sublist.
!             Use the programs input as an index into this filtered list.

Answer 12

Kotlin, 79 bytes

{n->var m=n;var i=0;var s="";while(m>0){val k="${++i*i}";if(k in s)m--;s+=k};i}

Try it online!

Answer 13

Wolfram Language (Mathematica), 75 bytes

(n=k=0;s="";While[n<#,If[!StringFreeQ[s,t=ToString[++k^2]],n++];s=s<>t];k)&

Try it online!

How it works

n keeps the number of early birds found so far, k the last number checked, s the string "1491625...". While n is too small, if s contains the next square, another early bird has been found, so we increment n. In any case, we extend s.

Once n reaches the input #, we return k, the last number checked and therefore the last early bird found.

On my laptop, takes about 53 seconds to compute the 53rd term of the sequence.

Answer 14

REXX, 66 bytes

arg n,a
k=0
do i=1 until k=n
  k=k+(pos(i*i,a)>0)
  a=a||i*i
  end
say i

Try it online!

Answer 15

Bash, 76 69 bytes

Assume n is given into variable (i.e. n=10 foo.sh). Uses package grep. Any middle value is output (if allowed, -3 bytes).

while((n));do((b=++a*a));grep -q $b<<<$s&&((n--));s=$s$b;done;echo $a

How does it work?

while ((n)); do  # while n != 0 (C-style arithmetic)
  ((b = ++a*a))  # Increment a and let b = a*a
    # Non-existent value is treated as zero
  grep $b<<<$s   # Search for b in s
    && ((n--))   # If found, decrement n
  s=$s$b         # Append b to s
done
echo $a