Concatenação decimal de quadrados

24

Premissa

Uma noite, eu estava apenas pensando em números. Descobri algo único sobre números como 7, 10, 12, 13 e mais. Eles são quadrados de quadrados! O que significa que, ao quadrado, são compostos pelos próprios quadrados. O OEIS os chama de quadrados, que são uma concatenação decimal de dois ou mais quadrados.

Exemplos de tais números incluem 7 (49 tem 2 2 e 3 2 ) 13 (169 tem 4 2 e 3 2 ) e 20 (400 tem 2 2 e 0 2 ). Outros exemplos incluem 37, pois 1369 é um termo que pode ser particionado como 1, 36 e 9. 1444 (38 2 ) é um termo que pode ser particionado como 1, 4, 4, 4. Perguntei sobre isso em Matemática .SE, e recebeu o nome de mim!

Desafio

Crie um programa que imprima os números do TanMath. Dado o número n (começando em 1), imprima o enésimo número do TanMath, T (n).

Como um exemplo de código:

>> 1
>> 7

ou

>> 4
>> 13

Referência à implementação do Python (obrigado @ MartinBüttner e @ 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

Aqui está uma lista dos 100 primeiros números:

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 350 369 370 375 379 380 390 397 400 402 405 408 410 413 420 430 440 441 450 460 470 475 480 487

Este é um código de golfe, então o código mais curto vence!

Boa sorte!

TanMath
fonte
38² também podem ser escritos 12² e 2², é claro.
Neil
@ Neil sim ... Está na lista dos 100 primeiros números.
TanMath
Desculpe se confundi você, mas eu estava apenas comentando a sua escolha de decomposição de 38² como 1² e 2² e 2² e 2².
Neil
@ Neil oh .. eu vejo. Vou deixar assim por enquanto, acho que é óbvio para os outros que 12 ^ 2 podem ser incluídos na decomposição.
TanMath

Respostas:

8

Pitão, 23 21 20 bytes

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

Graças a @isaacg por jogar fora 1 byte!

Experimente online.

Como funciona

                      (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.
Dennis
fonte
A complexidade do tempo de execução é catastrófica. Não recomendo tentar entradas com mais de 60 anos com o intérprete online.
Dennis
O té desnecessário, porque ^R2Znão conterá ^Z2. É o mesmo que o intervalo do Python, não inclui o topo.
Isaacg
Sim, percebi isso assim que li sua resposta. Isso foi uma sobra da abordagem anterior ... Obrigado!
Dennis
Na verdade, eu escrevi que, antes de ver sua postagem, minha internet está muito lenta e não vi sua atualização até depois da publicação. Não tentando roubar você ou algo assim.
Isaacg
11
Não se preocupe. Eu assumi que era algo assim. Você me ajudou muitas vezes antes. (E eu estou intimamente familiarizado com o problema de internet lenta: P.)
Dennis
5

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)

Isso cria uma função sem nome que aceita um número inteiro e retorna um número inteiro. Para chamá-lo, dê um nome, por exemplo 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

Agradecemos a Dennis por alguma ajuda e idéias e a Glen O por salvar 44 bytes!

Alex A.
fonte
4

JavaScript ES6, 126 127

A implementação de referência, convertida em Javascript com algum truque de golfe.

Usando eval para evitar retorno explícito.

Teste a execução do snippet abaixo em um navegador compatível com EcmaScript 6, com operador de propagação, parâmetros padrão e funções de seta (eu uso o 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>

edc65
fonte
3

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}

Uso

f(100)
=> 487

Explicação

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
}
user81655
fonte
0

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 é necessária

$ lua program.lua 1
7
$ lua program.lua 10
37
$ lua program.lua 100
487
Egor Skriptunoff
fonte
0

Python 3, 283 243 bytes

Esta é uma implementação de força bruta. Sugestões de golfe são bem-vindas.

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
Sherlock9
fonte