26
\$\begingroup\$

Premise

One night, I was just contemplating on numbers. I found out about something unique about numbers like 7, 10, 12, 13, and more. They are squares of squares! Meaning, that when squared, are comprised of squares themselves. The OEIS calls them Squares which are a decimal concatenation of two or more squares.

Examples of such numbers include 7 (49 has 22 and 32) 13 (169 has 42 and 32) and 20 (400 has 22 and 02). Other examples include 37, as 1369 is a term as it can be partitioned as 1, 36 and 9. 1444 (382) is a term as it can be partitioned as 1, 4, 4, 4. I asked about this on Math.SE, and it was named after me!

Challenge

Design a program that prints TanMath numbers. Given the number n (starting at 1), print the nth TanMath number, T(n).

As a code example:

>> 1
>> 7

or

>> 4
>> 13

Reference Python implementation(thanks @MartinBüttner and @Sp3000!):

from math import sqrt

n = input()

def r(digits, depth):
    z = len(digits)
    if z < 1:
        return (depth > 1)
    else:
        for i in range(1, z+1):
            t = int(digits[:i])
            if sqrt(t).is_integer() and r(digits[i:], depth+1):
                return True
        return False


i=0
t=0
while t < n:
    i += 1

    if r(str(i**2), 0):
        t += 1

print i

Here is a list of the first 100 numbers:

7 10 12 13 19 20 21 30 35 37 38 40 41 44 50 57 60 65 70 80 90 95 97 100 102 105 107 108 110 112 119 120 121 125 129 130 138 140 150 160 170 180 190 191 200 201 204 205 209 210 212 220 223 230 240 250 253 260 270 280 285 290 300 305 306 310 315 320 325 330 340 342 343 345 348 350 360 369 370 375 379 380 390 397 400 402 405 408 410 413 420 430 440 441 450 460 470 475 480 487

This is a code golf, so the shortest code wins!

Good luck!

\$\endgroup\$
4
  • \$\begingroup\$ 38² can also be written 12² & 2² of course. \$\endgroup\$
    – Neil
    Nov 14, 2015 at 1:27
  • \$\begingroup\$ @Neil yes...cIt is in the list of the first 100 numbers. \$\endgroup\$
    – TanMath
    Nov 14, 2015 at 1:29
  • \$\begingroup\$ Sorry if I've confused you, but I was just commenting on your choice of decomposition of 38² as 1² & 2² & 2² & 2². \$\endgroup\$
    – Neil
    Nov 14, 2015 at 1:36
  • \$\begingroup\$ @Neil oh.. I see. I will leave it like that for now, I think it is obvioud to others that 12^2 can be included in the decomposition. \$\endgroup\$
    – TanMath
    Nov 14, 2015 at 1:41

8 Answers 8

7
\$\begingroup\$

Pyth, 23 21 20 bytes

e.ff!-sMT^R2Z./`^Z2Q

Thanks to @isaacg for golfing off 1 byte!

Try it online.

How it works

                      (implicit) Store the evaluated input in Q.
 .f                Q  Filter; find the first Q positive integers Z such that:
                ^Z2     Compute the square of Z.
               `        Cast to string.
             ./         Compute all partitions of the string.
   f                    Filter; find all partitions T such that:
      sMT                 Cast all elements of T to integer.
         ^R2Z             Compute the squares of all integers in [0, ..., Z-1].
     -                    Remove the squares from the integers in T.
    !                     Compute the logical NOT of the result. This returns True
                          iff all integers in T are squares of numbers less than Z.
                        Keep T if `!' returned True.
                      Keep Z if `!' returned True for at least one T.
e                     Retrieve the last of the Q matches.
\$\endgroup\$
5
  • \$\begingroup\$ Run time complexity is catastrophic. I don't recommend trying inputs over 60 with the online interpreter. \$\endgroup\$
    – Dennis
    Nov 13, 2015 at 21:52
  • \$\begingroup\$ The t is unnecessary, because ^R2Z will not contain ^Z2. It's the same as Python's range, it doesn't include the top end. \$\endgroup\$
    – isaacg
    Nov 13, 2015 at 22:13
  • \$\begingroup\$ Yes, I realized that as soon as I read your answer. That was a leftover from the previous approach... Thanks! \$\endgroup\$
    – Dennis
    Nov 13, 2015 at 22:14
  • \$\begingroup\$ I actually wrote that before I saw your post, my internet is very slow and I didn't see your update until after I posted. Not trying to snipe you or anything. \$\endgroup\$
    – isaacg
    Nov 13, 2015 at 22:15
  • 1
    \$\begingroup\$ No worries. I assumed it was something like that. You have helped me many times before. (And I'm intimately familiar with the problem of slow internet. :P) \$\endgroup\$
    – Dennis
    Nov 13, 2015 at 22:19
5
\$\begingroup\$

Julia, 189 145 bytes

n->(c=m=0;while c<n m+=1;d=["$(m^2)"...];for p=partitions(d) d==[p...;]&&!any(√map(parse,map(join,p))%1.>0)&&endof(p)>1&&(c+=1;break)end;end;m)

This creates an unnamed function that accepts an integer and returns an integer. To call it, give it a name, e.g. f=n->....

Ungolfed:

function tanmath(n::Integer)
    # Initialize the number to check (c) and the nth TanMath
    # number (m) both to 0
    c = m = 0

    # While we've generated fewer than n TanMath numbers...
    while c < n
        # Increment the TanMath number
        m += 1

        # Get the digits of m^2 as characters
        d = ["$(m^2)"...]

        # Loop over the unordered partitions of the digits
        for p in partitions(d)
            # Convert the partition of digits to parsed numbers
            x = map(parse, map(join, p))

            # If the partition is in the correct order, none of the
            # square roots of the digits are non-integral, and p is
            # of length > 1...
            if d == [p...;] && !any(sqrt(x) % 1 .> 0) && endof(p) > 1
                # Increment the check
                c += 1

                # Leave the loop
                break
            end
        end
    end

    # Return the nth TanMath number
    return m
end

Thanks to Dennis for some help and ideas and thanks to Glen O for saving 44 bytes!

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

JavaScript ES6, 126 127

The reference implementation, converted to Javascript with some golf trick.

Using eval to avoid explicit return.

Test running the snippet below in an EcmaScript 6 compliant browser, with spread operator, default parameters and arrow functions (I use Firefox)

F=n=>eval('for(i=t=0;t<n;t+=k([...i*i+""]))++i',k=(s,l=1,n="")=>s[0]?s.some((d,i)=>Math.sqrt(n+=d)%1?0:k(s.slice(i+1),l-1)):l)

// Less golfed

U=n=>{
  k = (s,l=1,n="") =>
    s[0]
    ? s.some((d,i) => 
             Math.sqrt(n+=d)%1 ? 0 : k(s.slice(i+1),l-1)
            )
    : l;
  for(i=t=0; t<n; ) {
    ++i;
    t += k([...i*i+""])
  }  
  return i
}

function test() { R.innerHTML=F(+I.value) }

test()
<input id=I value=100><button onclick='test()'>-></button>
<span id=R></span>

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

JavaScript (ES6), 143 bytes

f=n=>{for(i=c=0;c<n;c+=1<g(++i*i+""))g=s=>{for(var l=0;s[l++];)if(!(Math.sqrt(s.slice(0,l))%1)&&!s[l]|(r=!!g(s.slice(l))))return 1+r};return i}

Usage

f(100)
=> 487

Explanation

f=n=>{
  for(
    i=                     // i = current number to check
      c=0;                 // c = number of TanMath numbers found so far
    c<n;                   // keep looping until we have found the required TanMath number
    c+=1<                  // increment the count if it has multiple squares in the digits
      g(++i*i+"")          // check if the current number is a TanMath number
  )
    g=s=>{                 // this function is passed a number as a string and returns the
                           //     number of squares found (max 2) or undefined if 0
      for(var l=0;s[l++];) // loop through each digit
                           // ('var' is necessary because the function is recursive)
        if(
          !(Math.sqrt(     // check if the square root of the digits is a whole number
            s.slice(0,l)   // get the digits to check
          )%1)&&
          !s[l]|           // finish if there are no more digits left to check
          (r=!!            // r = true if number of squares in remaining digits > 0
            g(s.slice(l))  // get number of squares in remaining digits
          )
        )
          return 1+r       // return number of squares found
    };
  return i                 // return the number that the loop finished at
}
\$\endgroup\$
2
\$\begingroup\$

Raku, 44 bytes

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

Try it online!

The runtime of this inflates fast, due to bruteforcing the combination of powers in the regex. If this were a instead, then the submission could just be that central codeblock instead.

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

Jelly, 14 12 bytes

²ŒṖḌṖƲPƇµ#Ṫ

Try it online!

How it works

²ŒṖḌṖƲPƇµ#Ṫ - Main link. Takes no arguments
         µ#  - Read n from STDIN and run the following over k = 1, 2, 3, ... until n integers return True:
²            -   Yield k²
 ŒṖ          -   Yield all partitions of k²'s digits
   Ḍ         -   Convert each list of digits back into a number
    Ʋ       -   Yield 1 for perfect squares and 0 otherwise
      PƇ     -   Remove all lists with any zeros
                This returns an empty list (falsy) for non-TanMath numbers
                 and a non-empty list (truthy) for TanMath numbers
           Ṫ - Return the last element i.e. the nth number for which the above is true
\$\endgroup\$
0
\$\begingroup\$

Lua, 148 bytes

c=...r=load"a=a or...==''for p=0,...and n-1or-1 do p='^'..p*p..'(.*)'r(p.match(...,p))end"n=-1repeat
n=n+1r(n*n)c,a=c-(a and 1or 0)until c<1print(n)

Lua 5.3 is required

$ lua program.lua 1
7
$ lua program.lua 10
37
$ lua program.lua 100
487
\$\endgroup\$
0
\$\begingroup\$

Python 3, 283 243 bytes

This is a brute-force implementation. Golfing suggestions welcome.

from itertools import*
def t(n):
 a=m=0
 while a<n:m+=1;d=str(m*m);r=range(1,len(d));c=[i*i for i in range(m)];a+=any(all(p in c for p in q)for q in[[int(d[x:y])for x,y in zip((0,)+j,j+(None,))]for i in r for j in combinations(r,i)])
 return m

Ungolfed:

import itertools
def tanmath(n):
    a = 0
    m = 0
    while a < n:
        m += 1
        d = str(m*m)
        squares = [i*i for i in range(m)]
        z = []
        # partitions code
        for i in range(1, len(d)):
            for j in itertools.combinations(range(1, len(d)), i):
                partition_indices = zip((0,)+j, j+(None,))
                z.append([int(d[x:y]) for x, y in partition_indices]
        # end partitions code
        if any(all(p in squares for p in q) for q in z):
            a += 1
    return m
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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