15
\$\begingroup\$

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, 72 (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 k2 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

\$\endgroup\$
  • \$\begingroup\$ Is the table of test cases using base 0 or 1? \$\endgroup\$ – idrougge Nov 23 '17 at 12:53
  • 1
    \$\begingroup\$ Can outputting the first n elements of the sequence be accepted? It's up to OP but many people choose to allow that. \$\endgroup\$ – HyperNeutrino Nov 23 '17 at 13:09
  • \$\begingroup\$ @idrougge test cases are 1-based. \$\endgroup\$ – James Holderness Nov 23 '17 at 13:10
  • \$\begingroup\$ @HyperNeutrino I'd prefer to have a consistent set of results for all answers, so please just return the single value of a(n). \$\endgroup\$ – James Holderness Nov 23 '17 at 13:13
  • \$\begingroup\$ Test cases up to 79. \$\endgroup\$ – user202729 Nov 24 '17 at 14:26

15 Answers 15

5
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ You can leave out the ½ as that will be automatically added to the loop when missing. \$\endgroup\$ – Adnan Nov 23 '17 at 15:13
  • \$\begingroup\$ @Adnan: True. Noticed this challenge just before I jumped on a train (or was going to if it hadn't been delayed), so I totally missed that. Thanks :) \$\endgroup\$ – Emigna Nov 23 '17 at 17:17
7
\$\begingroup\$

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!

\$\endgroup\$
6
\$\begingroup\$

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

Perl 5, 34 bytes

33 bytes code + 1 for -p.

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

Try it online!

\$\endgroup\$
4
\$\begingroup\$

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.

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

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

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!

\$\endgroup\$
  • \$\begingroup\$ lol you beat me to this; I had the exact same as your solution (after golfing) :P \$\endgroup\$ – HyperNeutrino Nov 23 '17 at 13:04
  • \$\begingroup\$ @HyperNeutrino Seems to be wrong, unfortunately. \$\endgroup\$ – user202729 Nov 23 '17 at 13:05
  • \$\begingroup\$ Oh really? That's unfortunate :( edit oh right the nfind thingy :((( \$\endgroup\$ – HyperNeutrino Nov 23 '17 at 13:05
  • \$\begingroup\$ @HyperNeutrino No problem, reading from stdin works. \$\endgroup\$ – user202729 Nov 23 '17 at 13:06
2
\$\begingroup\$

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!

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

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 ^^^?
\$\endgroup\$
  • \$\begingroup\$ Wow, has automatic stringification. \$\endgroup\$ – user202729 Nov 24 '17 at 13:34
2
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ I don’t know this language, but could you save any bytes by checking whether the current square is in the string before appending it? \$\endgroup\$ – WGroleau Nov 23 '17 at 16:06
  • \$\begingroup\$ @WGroleau I don't think so. The main check is still one byte (F instead of z), but the stack manipulation won't be any simpler, possibly even one or two commands worse. \$\endgroup\$ – Martin Ender Nov 23 '17 at 16:09
  • \$\begingroup\$ @JamesHolderness Why shouldn't it? 69696 appears two positions before its natural position (overlapping with it). If overlaps with its natural position should be disregarded, you should probably say so in the challenge. \$\endgroup\$ – Martin Ender Nov 23 '17 at 16:25
  • \$\begingroup\$ @JamesHolderness the relevant test cases were taking too long to check, so I just did up to 10. The intermediate test case should help. \$\endgroup\$ – Martin Ender Nov 23 '17 at 17:12
  • \$\begingroup\$ That definitely increases the challenge. Will you comment previous answers that fail the same way? Note: I find these entertaining, but never answer, because all of my languages were designed with readability as a requirement. :-) Except for assembler and FORTH. :-) \$\endgroup\$ – WGroleau Nov 23 '17 at 17:14
1
\$\begingroup\$

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

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!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ @James Here it goes. \$\endgroup\$ – iBug Nov 25 '17 at 17:05

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.