Dezimale Verkettung von Quadraten

24

Prämisse

Eines Nachts habe ich nur über Zahlen nachgedacht. Ich habe etwas Einzigartiges über Zahlen wie 7, 10, 12, 13 und mehr herausgefunden. Sie sind Quadrate von Quadraten! Das heißt, wenn sie quadriert sind, bestehen sie selbst aus Quadraten. Der OEIS nennt sie Quadrate, dh eine dezimale Verkettung von zwei oder mehr Quadraten.

Beispiele für solche Zahlen sind 7 (49 hat 2 2 und 3 2 ) 13 (169 hat 4 2 und 3 2 ) und 20 (400 hat 2 2 und 0 2 ). Andere Beispiele sind 37, da 1369 ein Begriff ist, der als 1, 36 und 9 unterteilt werden kann. 1444 (38 2 ) ist ein Begriff, der als 1, 4, 4, 4 unterteilt werden kann .SE, und es wurde nach mir benannt!

Herausforderung

Entwerfen Sie ein Programm, das TanMath-Zahlen druckt. Geben Sie die n-te TanMath-Zahl T (n) mit der Zahl n (beginnend bei 1) aus.

Als Codebeispiel:

>> 1
>> 7

oder

>> 4
>> 13

Referenz-Python-Implementierung (danke @ MartinBüttner und @ 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

Hier ist eine Liste der ersten 100 Zahlen:

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

Dies ist ein Codegolf, also gewinnt der kürzeste Code!

Viel Glück!

TanMath
quelle
38² kann natürlich auch 12² & 2² geschrieben werden.
Neil
@Neil ja ... cEs steht in der Liste der ersten 100 Nummern.
TanMath
Sorry , wenn ich habe Sie verwirrt, aber ich war nur zu kommentieren Ihrer Wahl der Zersetzung von 38² als 1½ & 2² & 2² & 2².
Neil
@Neil oh .. ich sehe. Ich werde jetzt ist es so lassen, ich denke , es obvioud zu anderen ist , dass 12 ^ 2 kann bei der Zersetzung enthalten sein.
TanMath

Antworten:

8

Pyth, 23 21 20 Bytes

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

Vielen Dank an @isaacg für das Golfen ab 1 Byte!

Probieren Sie es online aus.

Wie es funktioniert

                      (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
quelle
Die Komplexität der Laufzeit ist katastrophal. Ich empfehle nicht, Eingaben über 60 mit dem Online-Interpreter zu versuchen .
Dennis
Das tist unnötig, da ^R2Znicht enthalten ^Z2. Es ist das gleiche wie bei Python, enthält jedoch nicht das obere Ende.
isaacg
Ja, ich erkennen , dass, sobald ich Ihre Antwort lesen. Das war ein Überbleibsel aus dem vorherigen Ansatz ... Danke!
Dennis
Ich schrieb sogar , dass , bevor ich Ihren Beitrag gesehen, mein Internet ist sehr langsam und ich habe das Update erst , nachdem ich gebucht. Ich versuche nicht, dich oder irgendetwas zu schnappen.
isaacg
1
Keine Bange. Ich nahm an, dass es so etwas war. Du hast mir schon oft geholfen. (Und ich bin eng mit dem Problem des langsamen Internet vertraut: 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)

Dies schafft eine unbenannte Funktion, die eine ganze Zahl annimmt, und gibt eine ganze Zahl ist. Um es zu nennen, geben Sie ihm einen Namen, zf=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

Dank Dennis für etwas Hilfe und Ideen und dank Glen O für das Speichern von 44 Byte!

Alex A.
quelle
4

JavaScript ES6, 126 127

Die Referenzimplementierung, konvertiert nach Javascript mit ein paar Golfticks.

Verwenden von eval, um eine explizite Rückgabe zu vermeiden.

Testen Sie die Ausführung des folgenden Snippets in einem EcmaScript 6-kompatiblen Browser mit Spread-Operator, Standardparametern und Pfeilfunktionen (ich verwende 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
quelle
3

JavaScript (ES6), 143 Byte

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}

Verwendung

f(100)
=> 487

Erläuterung

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
quelle
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 erforderlich

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

Python 3, 283 243 Bytes

Dies ist eine Brute-Force-Implementierung. Golfen Vorschläge willkommen.

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
quelle