Десятичная конкатенация квадратов

24

посылка

Однажды ночью я просто размышлял о цифрах. Я узнал о чем-то уникальном о числах, таких как 7, 10, 12, 13 и более. Это квадраты квадратов! Это означает, что в квадрате они состоят из самих квадратов. OEIS называет их квадратами, которые представляют собой десятичное объединение двух или более квадратов.

Примеры таких чисел включают 7 (49 имеет 2 2 и 3 2 ) 13 (169 имеет 4 2 и 3 2 ) и 20 (400 имеет 2 2 и 0 2 ). Другие примеры включают 37, поскольку термин 1369 является термином, так как он может быть разделен как 1, 36 и 9. 1444 (38 2 ) - это термин, так как он может быть разделен как 1, 4, 4, 4. Я спрашивал об этом в Math .SE, и он был назван в честь меня!

Вызов

Разработайте программу, которая печатает номера TanMath. Учитывая число n (начиная с 1), выведите n-е число TanMath, T (n).

В качестве примера кода:

>> 1
>> 7

или

>> 4
>> 13

Ссылка на реализацию Python (спасибо @ MartinBüttner и @ 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

Вот список первых 100 номеров:

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

Это код гольф, поэтому выигрывает самый короткий код!

Удачи!

TanMath
источник
38² также может быть написано 12² & 2², конечно.
Нил
@ Нейл да ... он в списке первых 100 номеров.
TanMath
Извините, если я вас запутал, но я просто комментировал ваш выбор разложения 38² как 1² & 2² & 2² & 2².
Нил
@ Нил, ох ... Понятно. Я пока оставлю это так, я думаю, что для других очевидно, что 12 ^ 2 может быть включено в разложение.
TanMath

Ответы:

8

Pyth, 23 21 20 байт

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

Спасибо @isaacg за вывод 1 байта!

Попробуйте онлайн.

Как это работает

                      (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.
Деннис
источник
Сложность во время выполнения катастрофична. Я не рекомендую вводить более 60 с онлайн-переводчиком.
Деннис
Это tне нужно, потому ^R2Zчто не будет содержать ^Z2. Это то же самое, что диапазон Python, он не включает верхний конец.
Исаак
Да, я понял это, как только прочитал твой ответ. Это было пережитком предыдущего подхода ... Спасибо!
Денис
На самом деле я написал, что до того, как я увидел ваше сообщение, мой интернет работает очень медленно, и я не видел ваше обновление до тех пор, пока я не разместил сообщение. Не пытаюсь стрелять из вас или что-то еще.
Исаак
1
Не стоит беспокоиться. Я предположил, что это было что-то подобное. Вы помогали мне много раз прежде. (И я глубоко знаком с проблемой медленного интернета: P.)
Dennis
5

Юлия, 189 145 байтов

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)

Это создает безымянную функцию, которая принимает целое число и возвращает целое число. Чтобы назвать его, дайте ему имя, например 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

Спасибо Деннису за помощь и идеи, а также спасибо Glen O за сохранение 44 байтов!

Алекс А.
источник
4

JavaScript ES6, 126 127

Эталонная реализация, преобразованная в Javascript с некоторыми хитростями в гольф.

Использование eval, чтобы избежать явного возврата.

Протестируйте приведенный ниже фрагмент в браузере, совместимом с EcmaScript 6, с оператором распространения, параметрами по умолчанию и функциями стрелок (я использую 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
источник
3

JavaScript (ES6), 143 байта

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}

использование

f(100)
=> 487

объяснение

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
источник
0

Луа, 148 байт

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

$ lua program.lua 1
7
$ lua program.lua 10
37
$ lua program.lua 100
487
Егор Скриптунов
источник
0

Python 3, 283 243 байта

Это реализация грубой силы. Предложения по игре в гольф приветствуются.

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
источник