Rangkaian kotak desimal

24

Premis

Suatu malam, saya hanya merenungkan angka. Saya menemukan sesuatu yang unik tentang angka seperti 7, 10, 12, 13, dan banyak lagi. Mereka adalah kotak kuadrat! Arti, bahwa ketika kuadrat, terdiri dari kuadrat itu sendiri. OEIS memanggil mereka Kotak yang merupakan gabungan desimal dari dua atau lebih kotak.

Contoh angka-angka tersebut termasuk 7 (49 memiliki 2 2 dan 3 2 ) 13 (169 memiliki 4 2 dan 3 2 ) dan 20 (400 memiliki 2 2 dan 0 2 ). Contoh lain termasuk 37, karena 1369 adalah istilah karena dapat dipartisi sebagai 1, 36 dan 9. 1444 (38 2 ) adalah istilah karena dapat dipartisi sebagai 1, 4, 4, 4. Saya bertanya tentang hal ini pada Matematika .SE, dan diberi nama setelah saya!

Tantangan

Desain program yang mencetak angka TanMath. Diberi nomor n (mulai dari 1), cetak nomor TanMath ke-n, T (n).

Sebagai contoh kode:

>> 1
>> 7

atau

>> 4
>> 13

Referensi implementasi Python (terima kasih @ MartinBüttner dan @ 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

Berikut adalah daftar 100 angka pertama:

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

Ini adalah kode golf, jadi kode terpendek menang!

Semoga berhasil!

TanMath
sumber
38 ² juga dapat ditulis 12 ² & 2 ² tentu saja.
Neil
@Neil ya ... cIni ada dalam daftar 100 angka pertama.
TanMath
Maaf jika saya membingungkan Anda, tetapi saya baru saja mengomentari pilihan Anda untuk penguraian 38² sebagai 1² & 2² & 2² & 2².
Neil
@Neil oh .. Begitu. Saya akan membiarkannya seperti itu untuk saat ini, saya pikir tidak sopan bagi yang lain bahwa 12 ^ 2 dapat dimasukkan dalam dekomposisi.
TanMath

Jawaban:

8

Pyth, 23 21 20 byte

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

Terima kasih kepada @isaacg untuk bermain golf 1 byte!

Cobalah online.

Bagaimana itu bekerja

                      (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
sumber
Kompleksitas run time adalah bencana. Saya tidak merekomendasikan mencoba masukan lebih dari 60 dengan penerjemah online.
Dennis
Tidak tperlu, karena ^R2Ztidak akan mengandung ^Z2. Itu sama dengan jangkauan Python, itu tidak termasuk ujung atas.
isaacg
Ya, saya menyadari bahwa begitu saya membaca jawaban Anda. Itu adalah sisa dari pendekatan sebelumnya ... Terima kasih!
Dennis
Saya sebenarnya menulis bahwa sebelum saya melihat posting Anda, internet saya sangat lambat dan saya tidak melihat pembaruan Anda sampai setelah saya diposting. Tidak mencoba menembak Anda atau apa pun.
isaacg
1
Jangan khawatir. Saya mengira itu adalah sesuatu seperti itu. Anda telah membantu saya berkali-kali sebelumnya. (Dan aku intim akrab dengan masalah internet lambat: P.)
Dennis
5

Julia, 189 145 byte

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)

Ini menciptakan fungsi tanpa nama yang menerima integer dan mengembalikan integer. Untuk menyebutnya, berikan nama, mis f=n->....

Tidak Disatukan:

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

Terima kasih kepada Dennis untuk bantuan dan ide dan terima kasih kepada Glen O karena telah menghemat 44 byte!

Alex A.
sumber
4

JavaScript ES6, 126 127

Implementasi referensi, dikonversi ke Javascript dengan beberapa trik golf.

Menggunakan eval untuk menghindari pengembalian eksplisit.

Tes menjalankan cuplikan di bawah ini di peramban yang mendukung EcmaScript 6, dengan operator sebaran, parameter default dan fungsi panah (saya menggunakan 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
sumber
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}

Pemakaian

f(100)
=> 487

Penjelasan

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
}
pengguna81655
sumber
0

Lua, 148 byte

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)

Diperlukan Lua 5.3

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

Python 3, 283 243 byte

Ini adalah implementasi brute-force. Saran bermain golf diterima.

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

Tidak Disatukan:

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
sumber