Dziesiętna konkatenacja kwadratów

24

Przesłanka

Pewnej nocy zastanawiałem się nad liczbami. Dowiedziałem się czegoś wyjątkowego o liczbach 7, 10, 12, 13 i innych. Są to kwadraty kwadratów! Oznacza to, że gdy są podniesione do kwadratu, składają się z samych kwadratów. OEIS nazywa je kwadratami, które są dziesiętną konkatenacją dwóch lub więcej kwadratów.

Przykłady takich liczb obejmują 7 (49 ma 2 2 i 3 2 ) 13 (169 ma 4 2 i 3 2 ) i 20 (400 ma 2 2 i 0 2 ). Inne przykłady obejmują 37, ponieważ 1369 to termin, ponieważ można go podzielić na 1, 36 i 9. 1444 (38 2 ) to termin, ponieważ można go podzielić na 1, 4, 4, 4. Zapytałem o to na Matematyki .SE, a nazwa pochodzi ode mnie!

Wyzwanie

Zaprojektuj program, który drukuje liczby TanMath. Biorąc pod uwagę liczbę n (od 1), wydrukuj n-ty numer TanMath, T (n).

Jako przykład kodu:

>> 1
>> 7

lub

>> 4
>> 13

Odwołanie do implementacji Python (dzięki @ MartinBüttner i @ 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

Oto lista pierwszych 100 liczb:

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

To jest golf golfowy, więc wygrywa najkrótszy kod!

Powodzenia!

TanMath
źródło
38² można również zapisać 12² i 2² oczywiście.
Neil
@ Nee tak ... c Jest na liście pierwszych 100 liczb.
TanMath,
Przepraszam, jeśli cię pomyliłem, ale właśnie komentowałem twój wybór rozkładu 38² jako 1² i 2² oraz 2² i 2².
Neil
@ Nee oh .. Rozumiem. Na razie zostawię to tak, myślę, że dla innych oczywiste jest, że 12 ^ 2 może zostać uwzględnione w rozkładzie.
TanMath,

Odpowiedzi:

8

Pyth, 23 21 20 bajtów

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

Dzięki @isaacg za grę w golfa na 1 bajcie!

Wypróbuj online.

Jak to działa

                      (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
źródło
Złożoność w czasie wykonywania jest katastrofalna. Nie polecam wypróbowywania danych wejściowych powyżej 60 lat za pomocą tłumacza online.
Dennis
Jest tto niepotrzebne, ponieważ ^R2Znie będzie zawierało ^Z2. Jest taki sam, jak zakres Pythona, nie obejmuje górnego końca.
isaacg
Tak, zdałem sobie sprawę, że jak tylko przeczytam twoją odpowiedź. To pozostałość po poprzednim podejściu ... Dzięki!
Dennis
Właściwie napisałem, że zanim zobaczyłem twój post, mój internet jest bardzo wolny i nie widziałem twojej aktualizacji, dopóki nie opublikowałem. Nie próbuję cię zastrzelić ani nic.
isaacg
1
Bez obaw. Zakładałem, że to coś takiego. Pomogłeś mi wiele razy wcześniej. (I jestem ściśle zaznajomiony z problemem wolnego Internetu.: P)
Dennis
5

Julia, 189 145 bajtów

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)

Tworzy to nienazwaną funkcję, która akceptuje liczbę całkowitą i zwraca liczbę całkowitą. Aby to nazwać, nadaj mu nazwę, np f=n->....

Nie golfowany:

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

Podziękowania dla Dennisa za pomoc i pomysły oraz dzięki Glen O za uratowanie 44 bajtów!

Alex A.
źródło
4

JavaScript ES6, 126 127

Implementacja referencyjna, przekonwertowana na JavaScript z pewnymi sztuczkami golfowymi.

Używanie eval, aby uniknąć jawnego powrotu.

Przetestuj poniższy fragment kodu w przeglądarce zgodnej z EcmaScript 6, z operatorem rozprzestrzeniania, parametrami domyślnymi i funkcjami strzałek (używam Firefoksa)

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
źródło
3

JavaScript (ES6), 143 bajty

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}

Stosowanie

f(100)
=> 487

Wyjaśnienie

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
}
użytkownik 81655
źródło
0

Lua, 148 bajtów

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)

Wymagany jest Lua 5.3

$ lua program.lua 1
7
$ lua program.lua 10
37
$ lua program.lua 100
487
Egor Skriptunoff
źródło
0

Python 3, 283 243 bajtów

To implementacja brutalnej siły. Sugestie dotyczące gry w golfa mile widziane.

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

Nie golfowany:

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
źródło