Concaténation décimale des carrés

24

Prémisse

Une nuit, je réfléchissais simplement aux chiffres. J'ai découvert quelque chose d'unique au sujet des nombres comme 7, 10, 12, 13 et plus. Ce sont des carrés de carrés! Cela signifie que lorsqu'ils sont au carré, ils sont eux-mêmes composés de carrés. L'OEIS les appelle des carrés qui sont une concaténation décimale de deux carrés ou plus.

Des exemples de tels nombres incluent 7 (49 a 2 2 et 3 2 ) 13 (169 a 4 2 et 3 2 ) et 20 (400 a 2 2 et 0 2 ). D'autres exemples incluent 37, car 1369 est un terme car il peut être partitionné en 1, 36 et 9. 1444 (38 2 ) est un terme car il peut être partitionné en 1, 4, 4, 4. J'ai demandé à ce sujet sur Math .SE, et il a été nommé d'après moi!

Défi

Concevez un programme qui imprime les nombres TanMath. Étant donné le nombre n (à partir de 1), imprimez le nième nombre TanMath, T (n).

Comme exemple de code:

>> 1
>> 7

ou

>> 4
>> 13

Référence à l'implémentation de Python (merci @ MartinBüttner et @ 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

Voici une liste des 100 premiers numéros:

7 10 12 13 19 20 21 30 35 37 38 40 41 44 50 57 60 65 70 80 90 95 97100 102 105 107 108 110 112 119 120 121 125 129 130 138 140 150 160 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

C'est un golf de code, donc le code le plus court gagne!

Bonne chance!

TanMath
la source
38² peut aussi s'écrire 12² & 2² bien sûr.
Neil
@Neil oui ... cIl est dans la liste des 100 premiers chiffres.
TanMath
Désolé si je vous ai dérouté, mais je commentais juste votre choix de décomposition de 38² en 1² & 2² & 2² & 2².
Neil
@Neil oh .. je vois. Je vais le laisser comme ça pour l'instant, je pense qu'il est évident pour les autres que 12 ^ 2 peuvent être inclus dans la décomposition.
TanMath

Réponses:

8

Pyth, 23 21 20 octets

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

Merci à @isaacg d'avoir joué au golf sur 1 octet!

Essayez-le en ligne.

Comment ça marche

                      (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
la source
La complexité du temps d'exécution est catastrophique. Je ne recommande pas d'essayer des entrées de plus de 60 avec l'interpréteur en ligne.
Dennis
Le tn'est pas nécessaire, car ^R2Zne contiendra pas ^Z2. C'est la même chose que la gamme Python, elle n'inclut pas l'extrémité supérieure.
isaacg
Oui, je m'en suis rendu compte dès que j'ai lu votre réponse. C'était un reste de l'approche précédente ... Merci!
Dennis
En fait, j'ai écrit qu'avant de voir votre message, mon Internet est très lent et je n'ai vu votre mise à jour qu'après avoir posté. Ne pas essayer de vous tirer dessus ou quoi que ce soit.
isaacg
1
Pas de soucis. J'ai supposé que c'était quelque chose comme ça. Vous m'avez aidé plusieurs fois auparavant. (Et je connais intimement le problème de l'internet lent.: P)
Dennis
5

Julia, 189145 octets

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)

Cela crée une fonction sans nom qui accepte un entier et renvoie un entier. Pour l'appeler, donnez-lui un nom, par exemple f=n->....

Non golfé:

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

Merci à Dennis pour son aide et ses idées et merci à Glen O pour avoir économisé 44 octets!

Alex A.
la source
4

JavaScript ES6, 126 127

L'implémentation de référence, convertie en Javascript avec quelques astuces de golf.

Utiliser eval pour éviter un retour explicite.

Testez l'exécution de l'extrait ci-dessous dans un navigateur compatible EcmaScript 6, avec l'opérateur d'étalement, les paramètres par défaut et les fonctions fléchées (j'utilise 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
la source
3

JavaScript (ES6), 143 octets

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

Explication

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
la source
0

Lua, 148 octets

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 est requis

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

Python 3, 283 243 octets

Il s'agit d'une implémentation par force brute. Suggestions de golf bienvenues.

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

Non golfé:

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
la source