Consider a sequence of natural numbers for which N appears as a substring in N^2. A018834

Output the nth element of this sequence.

Rules

Program takes only n as input and outputs just one number - N.

The sequence can be 0-indexed or 1-indexed.

Sequence: 1 5 6 10 25 50 60 76 100 250 376 500 600 625 760 ...
Squares:  1 25 36 100 625 2500 3600 5776 10000 62500 141376 250000 360000 390625 577600 ...

This is code-golf so shortest code wins.

  • 1
    A lot of implementations will run into problems (for me its due to not being able to create arrays with more than 2^32 values), which will make most solutions bound to a maximum size by default. Should these solutions be disqualified? – maxb Nov 28 at 9:23
  • 1
    @maxb I think theoretically was meant as not necessarily practically. – Arnauld Nov 28 at 9:24
  • 1
    @Ourous I know it's really low, that's why I don't like my solution. I could add a byte and have it work for much bigger inputs, so I'll add that as an alternative – maxb Nov 28 at 9:29
  • 1
    "N appears in N^2" would be better worded as something like "the decimal digits of N is a [contiguous] substring of the decimal digits of N squared" (11 does not "appear in" 121). [Strictly "contiguous" is redundant, but adding it is clear.] – Jonathan Allan Nov 28 at 10:53
  • 1
    @JonathanAllan Alternate suggested rewording: "N is lexicographically present in N^2" – Οurous Nov 28 at 10:57

20 Answers 20

05AB1E, 6 bytes

1-indexed

µNNnNå

Try it online!

Explanation

µ         # loop over increasing N until counter equals input
 N        # push N (for the output)
  Nn      # push N^2
    N     # push N
     å    # push N in N^2
          # if true, increase counter
  • That µ command is just... I wish I had that. – maxb Nov 28 at 9:57
  • @maxb: It is quite practical for challenges where you need to find the Nth number that meets a specific condition. – Emigna Nov 28 at 10:09
  • "if true, increase counter"? – Jonathan Allan Nov 28 at 11:43
  • @JonathanAllan: As in, "If N is contained in N^2 increase the value of the counter by 1". I should probably have written "increment counter". – Emigna Nov 28 at 11:48
  • I actually didn't understand the explanation; it appears that if å yields true then we have the current N at the top of the stack (increment counter and increment N), but if not we continue (increment N). Maybe use something other than "N" since that is the final result in the question body :p – Jonathan Allan Nov 28 at 11:59

Perl 6, 33 31 bytes

-2 bytes thanks to nwellnhof

{(grep {$^a²~~/$a/},1..*)[$_]}

Try it online!

Explanation:

{                            }  # Anonymous code block that returns
 (                      )[$_]   # The nth index of
  grep {          },1..*        # Filtering from the natural numbers
        $^a²                    # If the square of the number
            ~~/$a/              # Contains the number

JavaScript (ES6), 43 bytes

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

Try it online!


Non-recursive version, 47 bytes

n=>eval("for(k=0;n-=!!(++k*k+'').match(k););k")

Try it online!

  • This gives up to n=23 only? – Vedant Kandoi Nov 28 at 8:47
  • @VedantKandoi It depends on the size of the call stack in your JS engine. But computing \$a(n)\$ requires \$a(n)\$ recursions, so that's \$7600\$ recursive calls for \$n=23\$. – Arnauld Nov 28 at 8:55

MathGolf, 8 bytes (works for any input in theory, but only for n<10 in practice)

úrgɲï╧§

Try it online!

Alternative (works for n<49 in practice and theory)

►rgɲï╧§

The only difference is that instead of creating a list with 10^(input) values, I create a list with 10^6 items. This takes a while to run, so you could swap the first byte to any other 1-byte literal to test it out.

Explanation

ú          pop(a), push(10**a)
 r         range(0, n)
  g        filter array by...
   É       start block of length 3
    ²      pop a : push(a*a)
     ï     index of current loop
      ╧    pop a, b, a.contains(b)
           Block ends here
       §   get from array

The reason why this solution doesn't handle large input is that I noticed that the sequence grows less than exponentially, but more than any polynomial. That's why I used the 10**n operator (I wanted to use 2**n but it failed for input 1). That means that I create an extremely large array even for small inputs, just to filter out the vast majority of it, and then take one of the first elements. It's extremely wasteful, but I couldn't find another way to do it without increasing the byte count.

Common Lisp, 95 bytes

(lambda(n)(do((i 0))((= n 0)i)(if(search(format()"~d"(incf i))(format()"~d"(* i i)))(decf n))))

Try it online!

Clean, 83 bytes

import StdEnv,Text

(!!)[i\\i<-[1..]|indexOf(""<+i)(""<+i^2)>=0]

Try it online!

(!!)                               // index into the list of
 [ i                               // i for every
  \\ i <- [1..]                    // i from 1 upwards
  | indexOf (""<+i) (""<+i^2) >= 0 // where i is in the square of i
 ]

Jelly, 6 bytes

1ẇ²$#Ṫ

1-indexed.

Try it online!

How?

Finds the first n of the sequence as a list and then yields the tail, N.

1ẇ²$#Ṫ - Link: integer, n (>0)
1      - initialise x to 1
    #  - collect the first n matches, incrementing x, where:
   $   -   last two links as a monad:
  ²    -     square x
 ẇ     -     is (x) a substring of (x²)?
       -     (implicitly gets digits for both left & right arguments when integers)
     Ṫ - tail

If 0 were considered a Natural number we could use the 1-indexed full-program ẇ²$#Ṫ for 5.

Japt, 12 11 bytes

@aJ±X²søY}f

Try it

ȲsøY «U´}a

Try it

Ruby, 45 bytes

->n,i=1{/#{i+=1}/=~"#{i*i}"&&n-=1while n>0;i}

Try it online!

Java 8, 66 65 63 bytes

n->{int r=0;for(;!(++r*r+"").contains(r+"")||--n>0;);return r;}

-1 byte thanks to @Shaggy.
-2 bytes thanks to @Arnauld.

1-indexed.

Try it online.

Explanation:

n->{                // Method with integer as both parameter and return-type
  int r=0;          //  Result-integer, starting at 0
  for(;             //  Loop as long as:
       !(++r*r+"")  //    (increase result `r` by 1 first with `++r`)
                    //    If the square of the result `r` (as String) 
        .contains(  //    does not contain
          r+"")||   //    the result `r` itself (as String):
       --n>0;);     //     (decrease input `n` by 1 first with `--n`)
                    //     And continue looping if input `n` is not 0 yet
  return r;}        //  Return the result `r`

Clojure, 81 bytes

(fn[n](nth(filter #(clojure.string/includes?(str(* % %))(str %))(range))n))

Try it online! (Unfortunately, TIO doesn't seem to support Clojure's standard string library)

If Clojure had shorter importing syntax, or had a includes? method in the core library, this could actually be somewhat competitive. clojure.string/includes? alone is longer than some answers here though :/

(defn nth-sq-subs [n]
  (-> ; Filter from an infinite range of numbers the ones where the square of
      ;  the number contains the number itself
    (filter #(clojure.string/includes? (str (* % %)) (str %))
            (range))

    ; Then grab the "nth" result. Inc(rementing) n so 0 is skipped, since apparently
    ;  that isn't in the sequence
    (nth (inc n))))

Since the TIO link is broken, here's a test run. The number on the left is the index (n), and the result (N) is on the right:

(mapv #(vector % (nth-sq-subs %)) (range 100))
=>
[[0 1]
 [1 5]
 [2 6]
 [3 10]
 [4 25]
 [5 50]
 [6 60]
 [7 76]
 [8 100]
 [9 250]
 [10 376]
 [11 500]
 [12 600]
 [13 625]
 [14 760]
 [15 1000]
 [16 2500]
 [17 3760]
 [18 3792]
 [19 5000]
 [20 6000]
 [21 6250]
 [22 7600]
 [23 9376]
 [24 10000]
 [25 14651]
 [26 25000]
 [27 37600]
 [28 50000]
 [29 60000]
 [30 62500]
 [31 76000]
 [32 90625]
 [33 93760]
 [34 100000]
 [35 109376]
 [36 250000]
 [37 376000]
 [38 495475]
 [39 500000]
 [40 505025]
 [41 600000]
 [42 625000]
 [43 760000]
 [44 890625]
 [45 906250]
 [46 937600]
 [47 971582]
 [48 1000000]
 [49 1093760]
 [50 1713526]
 [51 2500000]
 [52 2890625]
 [53 3760000]
 [54 4115964]
 [55 5000000]
 [56 5050250]
 [57 5133355]
 [58 6000000]
 [59 6250000]
 [60 6933808]
 [61 7109376]
 [62 7600000]
 [63 8906250]
 [64 9062500]
 [65 9376000]
 [66 10000000]
 [67 10050125]
 [68 10937600]
 [69 12890625]
 [70 25000000]
 [71 28906250]
 [72 37600000]
 [73 48588526]
 [74 50000000]
 [75 50050025]
 [76 60000000]
 [77 62500000]
 [78 66952741]
 [79 71093760]
 [80 76000000]
 [81 87109376]
 [82 88027284]
 [83 88819024]
 [84 89062500]
 [85 90625000]
 [86 93760000]
 [87 100000000]
 [88 105124922]
 [89 109376000]
 [90 128906250]
 [91 146509717]
 [92 177656344]
 [93 200500625]
 [94 212890625]
 [95 250000000]
 [96 250050005]
 [97 289062500]
 [98 370156212]
 [99 376000000]]

This should be able to support any value of n; providing you're willing to wait for it to finish (finding the 50th to 100th integers in the sequence took like 15 minutes). Clojure supports arbitrarily large integer arithmetic, so once numbers start getting huge, it starts using BigInts.

Charcoal, 25 bytes

Nθ≔¹ηWθ«≦⊕η¿№I×ηηIη≦⊖θ»Iη

Try it online! Link is to verbose version of code. 0-indexed. Explanation:

Nθ

Input n.

≔¹η

Start N at 1. (Or, this could start counting at 0 which would make the input 1-indexed.)

Wθ«

Repeat until we have found n numbers in the sequence.

≦⊕η

Increment N.

¿№I×ηηIη

If N*N contains N, then...

≦⊖θ»

... decrement n.

Iη

Print N.

My attempts at golfing this further were stymied by Charcoal a) not having an if..then except at the end of a block (which costs 2 bytes) b) not having a Contains operator (converting the output of Find or Count into a boolean that I could subtract from n again costs 2 bytes).

Edit (response to comments): Python 2, 76 bytes

Wanted to try for a non recursive method. (New to golfing, any tips would be great!)

def f(c,n=0):
    while 1:
        if`n`in`n*n`:
            if c<2:return n
            c-=1
        n+=1

Thanks both BMO and Vedant Kandoi!

  • 2
    You don't have to count print(f(13)) in the code. Also while 1:,if c==1:return n,c==1 can be c<2 – Vedant Kandoi Nov 28 at 10:03
  • Ah, I didn't see that you wanted a non-recursive version, nvm.. Anyway, I currently count 76 bytes not 79. – BMO Nov 28 at 12:46
  • And you can save a few more: The spaces before & after ` are redundant and the one after c<2: too, next you can mix tabs and spaces for indentation (as shown here): 69 bytes Btw. there is no need to keep your old version (it's in the edit history for those who are interested) and why not link to TIO (or similar)/use the template from there? – BMO Nov 28 at 12:46

Haskell, 60 bytes

([n^2|n<-[1..],elem(show n)$words=<<mapM(:" ")(show$n^2)]!!)

Try it online!

      n<-[1..]              -- loop n through all numbers starting with 1
 [n^2|        ,    ]        -- collect the n^2 in a list where
     elem(show n)           -- the string representation of 'n' is in the list
       words ... (show$n^2) -- which is constructed as follows:

            show$n^2        -- turn n^2 into a string, i.e. a list of characters
          (:" ")            -- a point free functions that appends a space
                            -- to a character, e.g.  (:" ") '1' -> "1 "
        mapM                -- replace each char 'c' in the string (n^2) with
                            -- each char from (:" ") c and make a list of all
                            -- combinations thereof.
                            -- e.g. mapM (:" ") "123" -> ["123","12 ","1 3","1  "," 23"," 2 ","  3","   "]
      words=<<              -- split each element into words and flatten to a single list
                            -- example above -> ["123","12","1","3","1","23","2","3"]

(                      !!)  -- pick the element at the given index

Python 2, 47 43 bytes

-4 bytes thanks to Dennis (adding 1 to recursive call instead of returning n-1)

f=lambda c,n=1:c and-~f(c-(`n`in`n*n`),n+1)

Try it online!

Explantion/Ungolfed

Recursive function taking two arguments \$c,n\$; \$n\$ is counts up \$1,2,3\dots\$ and everytime \$n \texttt{ in } n^2\$ it decrements \$c\$. The recursion ends as soon as \$c = 0\$:

# Enumerating elements of A018834 in reverse starting with 1
def f(counter, number=1):
    # Stop counting
    if counter == 0:
        return 0
    # Number is in A018834 -> count 1, decrement counter & continue
    elif `number` in `number ** 2`:
        return f(counter-1, number+1) + 1
    # Number is not in A018834 -> count 1, continue
    else:
        return f(counter, number+1) + 1

APL (Dyalog Extended), 31 30 bytes

1∘{>⍵:⍺-1⋄(⍺+1)∇⍵-∨/(⍕⍺)⍷⍕⍺×⍺}

Try it online!

0-indexed.

Perl 5 -p, 33 bytes

map{1while++$\**2!~/${\}/}1..$_}{

Try it online!

Lua, 137 123 79 bytes

-thanks @Jo King for 44 bytes

n=io.read()i=0j=0while(i-n<0)do j=j+1i=i+(n.find(j*j,j)and 1or 0)end
print(j*j)

Try it online!

  • 79 bytes. Some generic tips; false/true can be 0>1/0<1, brackets aren't necessary for ifs and whiles, you can remove most whitespace after numbers (even newlines). – Jo King Nov 30 at 12:01

Tcl, 82 bytes

proc S n {while 1 {if {[regexp [incr i] [expr $i**2]]&&[incr j]==$n} {return $i}}}

Try it online!

  • I think you can mix the while and the if with: proc S n {while {[incr j [regexp [incr i] [expr $i**2]]]-$n} {};return $i} – david Dec 8 at 14:41

Tidy, 24 bytes

{x:str(x)in'~.x^2}from N

Try it online!

Returns a lazy list which, when called like a function, returns the nth element in the series.

Explanation

{x:str(x)in'~.x^2}from N
{x:              }from N       select all natural numbers `x` such that
   str(x)                      the string representation of `x`
         in                    is contained in
           '~.x^2              "~" + str(x^2)

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.