Теоретически выведите число Грэма

44

Число Грэма Gопределяется следующим образом:

u(3,n,1) = 3^n
u(3,1,m) = 3
u(3,n,m) = u(3,u(3,n-1,m),m-1)
[Knuth's up-arrow notation]
[Conway chained arrow notation]

THEN

g1 = u(3,3,4)
g2 = u(3,3,g1)
g3 = u(3,3,g2)
...
G = u(3,3,g63)

Вам дано это u(3,3,2)=7625597484987проверить ваш код.

Ваша задача - написать программу / функцию, которая будет выводить значение Gдетерминистически, учитывая достаточный размер целого числа и достаточно времени.

Ссылки

Leaderboard

Показать фрагмент кода

code-golf number-theory Дрянная Монахиня
источник
2
Относящиеся .
Утренняя монахиня,
7
Допускается ли случайность? Если я просто выведу случайные значения, в конечном итоге число Грэма должно быть получено.
миль
15
@ миль Почему на земле это уже не стандартная лазейка? Уточнено.
Дрянная Монахиня
18
Предупреждение: u (3, 3, 2) = u (3, 2, 3) = 7625597484987, поэтому вам также нужно проверить другие значения, такие как u (3, 5, 1) = 243, чтобы убедиться, что вы получили порядок аргументов правильный.
Андерс Касеорг
2
Номер Грэма?
Бета-распад

Ответы:

48

Двоичное лямбда-исчисление , 114 бит = 14,25 байт

HexDump:

00000000: 4457 42b0 2d88 1f9d 740e 5ed0 39ce 80    DWB.-...t.^.9..

Binary:

010001000101011101000010101100000010110110001000000111111001110101110100000011100101111011010000001110011100111010

объяснение

01 00                                           (λx.
│    01 00                                        (λy.
│    │    01 01 01 110                              x
│    │    │  │  └─ 10                               y
│    │    │  └─ 00                                  (λm.
│    │    │       01 01 01 10                         m
│    │    │       │  │  └─ 00                         (λg.
│    │    │       │  │       00                         λn.
│    │    │       │  │         01 01 10                  n
│    │    │       │  │         │  └─ 110                 g
│    │    │       │  │         └─ 00                     (λz.
│    │    │       │  │              10                     z))
│    │    │       │  └─ 00                            (λn.
│    │    │       │       00                            λf.
│    │    │       │         01 111110                    x
│    │    │       │         └─ 01 110                    (n
│    │    │       │            └─ 10                      f))
│    │    │       └─ 1110                             x)
│    │    └─ 10                                     y)
│    └─ 00                                        (λf.
│         00                                        λz.
│           01 110                                   f
│           └─ 01 01 1110                            (x
│              │  └─ 110                              f
│              └─ 10                                  z)))
└─ 00                                           (λf.
     00                                           λz.
       01 110                                      f
       └─ 01 110                                   (f
          └─ 01 110                                 (f
             └─ 10                                   z)))

Это (λ x . (Λ y . X y (λ m . M (λ g . Λ n . N g 1) (λ n . Λ f . X ( n f )) x ) y ) (λ f . Λ z . f ( x f z ))) 3, где все числа представлены в виде церковных цифр, Церковные цифры являются стандартным представлением лямбда-исчисления натуральных чисел, и они хорошо подходят для этой задачи, потому что церковный номер определяется итерацией функции: n g является n- й итерацией функции g .

Например, если g - функция λ n . λ ф . 3 ( n f ), который умножает 3 на церковную цифру, то λ n . n g 1 - это функция, которая переводит 3 в степень церковной цифры. Повторение этой операции m раз дает

m (λ g . λ n . n g 1) (λ n . λ f . 3 ( n f )) n = u (3, n , m ).

(Мы используем умножение u (-, -, 0), а не возведение в степень u (-, -, 1) в качестве базового случая, потому что вычитание 1 из церковного числа неприятно .)

Подставим n = 3:

m (λ g . λ n . n g 1) (λ n . λ f . 3 ( n f )) 3 = u (3, 3, m ).

Повторение этой операции 64 раза, начиная с m = 4, дает

64 (λ м . М (λ г . Λ п . П г 1) (λ п . Λ е . 3 ( п е )) 3) 4 = О .

Чтобы оптимизировать это выражение, подставьте 64 = 4 ^ 3 = 3 4:

3 4 (λ м . М (λ г λ. П . П г 1) (λ п . Λ е . 3 ( п е )) 3) 4 = О .

Помните 4 = succ 3 = λ f . λ z . f (3 f z ) в качестве лямбда-аргумента:

(λ y . 3 y (λ m . m (λ g . λ n . n g 1) (λ n . λ f . 3 ( n f )) 3) y ) (λ f . λ z . f (3 f г )) = G .

Наконец, запомните 3 = λ f . λ z . f ( f ( f z )) в качестве лямбда-аргумента:

(λ x . (λ y . x y (λ m . m (λ g . λ n . n g 1) (λ n . λ f . x ( n f )) x ) y ) (λ f . λ z . е ( х е г ))) 3 = О .

Андерс Касеорг
источник
Где можно найти переводчика для этого языка?
Деннис
4
У @Dennis tromp.github.io/cl/cl.html есть пара из них.
Андерс Касеорг
1
Это потрясающе . это заслуживает значительной награды
кошка
1
14.25 bytesпохоже портит таблицу лидеров. Он анализируется как 25 bytes, и поэтому вы ставитесь на второе место.
Дан
1
@ Думаю, я исправил фрагмент таблицы лидеров.
Андерс Касеорг
40

Haskell, 41 байт

i=((!!).).iterate
i(($3).i(`i`1)(*3))4 64

Объяснение:

(`i`1)f n= i f 1 nвычисляет nитерацию функции, fначиная с 1. В частности, (`i`1)(*3)n= 3 ^ n , и повторение этой конструкции m раз дает i(`i`1)(*3)m n= u (3, n , m ). Мы можем переписать это как (($n).i(`i`1)(*3))m= u (3, n , m ) и повторить эту конструкцию k раз, чтобы получить i(($3).i(`i`1)(*3))4 k= g _ k .

Андерс Касеорг
источник
16

Haskell, 43 байта

q=((!!).).iterate
g=q(`q`1)(3*)
q(`g`3)4$64

Там был лучший способ перевернуть в gлинию.

46 байтов:

i=iterate
n%0=3*n
n%m=i(%(m-1))1!!n
i(3%)4!!64

48 байтов:

n%1=3^n
1%m=3
n%m=(n-1)%m%(m-1)
iterate(3%)4!!64

Просто записываю определения.

Базовые случаи немного более чистые, резервное копирование до 0, хотя это не экономит байты. Возможно, это облегчит написание альтернативного определения.

n%0=3*n
0%m=1
n%m=(n-1)%m%(m-1)
z=iterate(3%)2!!1
XNOR
источник
Можете ли вы использовать другую функцию, которая имеет приоритет ниже, чем +для удаления скобок между m-1?
Дрянная Монахиня
Я считаю 44 байта, а что случилось с 4 и 64?
Утренняя монахиня
К сожалению, я скопировал в моем тесте меньшего параметра. Я не думаю, что смогу изменить приоритет оператора, потому что я определяю новую функцию, которая имеет приоритет по умолчанию. Я не могу перезаписать существующую функцию.
xnor
Я имею в виду, я считаю 44 байта после того, как вы изменили его обратно на 64.
Leaky Nun
Я думаю, что вы имеете в виду (`g`3), нет (3`g`).
Андерс Касеорг
10

Pyth, 25 байт

M?H.UgbtH*G]3^3Gug3tG64 4

Первая часть M?H.UgbtH*G]3^3Gопределяет метод g(G,H) = u(3,G,H+1).

Для того, чтобы проверить первую часть, убедитесь , что 7625597484987=u(3,3,2)=g(3,1): g3 1.

Вторая часть ug3tG64 4начинается с, r0 = 4а затем вычисляется rn = u(3,3,r(n-1)) = g(3,r(n-1))64 раза, выводя окончательное значение ( rвыбирается вместо того, gчтобы избежать путаницы).

Чтобы проверить эту часть, начните с , r0=2а затем вычислить r1: ug3tG1 2.

Дрянная Монахиня
источник
Если g (G, H) = u (3, G, H + 1), вы должны иметь r (n) = u (3, 3, r (n - 1)) = g (3, r (n - 1) ) - 1), а не g (3, r (n - 1)). Я думаю, что ваш код
верен,
Вы можете сохранить байт, используя смещенные аргументы u ( ^3↦ *3, tG↦ G) и другой байт с помощью .UgbtH*G]3↦ e.ugNtHG1.
Андерс Касеорг
Альтернативный способ сохранить этот второй байт - *G]3↦ ShG.
Андерс Касеорг
8

Sesos , 30 байт

0000000: 286997 2449f0 6f5d10 07f83a 06fffa f941bb ee1f33  (i.$I.o]...:....A...3
0000015: 065333 07dd3e 769c7b                              .S3..>v.{

разобранный

set numout
add 4
rwd 2
add 64
jmp
    sub 1
    fwd 3
    add 3
    rwd 1
    add 1
    jmp
        sub 1
        jmp
            fwd 1
            jmp
                jmp
                    sub 1
                    fwd 1
                    add 1
                    rwd 1
                jnz
                rwd 1
                jmp
                    sub 1
                    fwd 3
                    add 1
                    rwd 3
                jnz
                fwd 3
                jmp
                    sub 1
                    rwd 2
                    add 1
                    rwd 1
                    add 1
                    fwd 3
                jnz
                rwd 1
                sub 1
            jnz
            rwd 1
            jmp
                sub 1
            jnz
            add 1
            rwd 1
            sub 1
        jnz
        fwd 1
        jmp
            sub 1
            rwd 1
            add 3
            fwd 1
        jnz
        rwd 2
    jnz
    rwd 1
jnz
fwd 2
put

Или в обозначении Brainfuck:

++++<<++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
[->>>+++<+[-[>[[->+<]<[->>>+<<<]>>>[-<<+<+>>>]<-]<[-]+<-]>[-<+++>]<<]<]>>.

тестирование

Для вычисления U (3, п , U (3, п ... у (3, п , м ) ...)) с K вложенных вызовов функции и заменить первые три addинструкций add 4, add 64, add 3с add m, add k, add nсоответственно. Поскольку Sesos не может строить числа быстрее, чем за линейное время, вы практически ограничены небольшими значениями, такими как u (3, 2, 2) = 27, u (3, 5, 1) = 243 и u (3, 1 , u (3, 1,… u (3, 1, m )…)) = 3.

Андерс Касеорг
источник
Вы можете заменить [-]с , ,так как EOF является 0.
mbomb007
6

JavaScript (ES7), 63 байта

u=(n,m)=>n>1&m>1?u(u(n-1,m),m-1):3**n
g=n=>n?u(3,g(n-1)):4
g(64)
Нил
источник
@AndersKaseorg Тьфу, в таком случае я могу отменить это изменение.
Нил
Это вызывает переполнение стека, может потребоваться перепроверить ваш шаблон рекурсии.
NodeNodeNode
Это не просто ES7. Это неограниченный ES7 (воображаемый вариант ES7, но с bignum, способный бесконечно оракулировать и использующий десятичную дробь с / # xE ^ в качестве сокращения).
user75200
5

Брахилог , 57 байт

4:64:1iw
:3{[1:N],3:N^.|t1,3.|hM:1-X,?t:1-:Mr:2&:Xr:2&.}.

Не ожидает ввода или вывода и записывает результат в STDOUT. Это приведет к переполнению стека в одной точке.

Для того, чтобы проверить , что это работает для малых значений (например u(3,3,2)) , вы можете заменить 4со значением mи 64с 1.

объяснение

Это в основном прямая реализация объясненного способа вычисления числа.

  • Основной предикат:

    4:64:1i                    Call Predicate 1 64 times with 4 as initial input (the second
                           call takes the output of the first as input, etc. 64 times).
       w                   Write the final output to STDOUT

  • Предикат 1:

    :3{...}.                   Call predicate 2 with input [Input, 3]. Its output is the 
                           output of predicate 1.

  • Предикат 2:

    [1:N],                     M = 1
      3:N^.                Output = 3^N
|                          Or
t1,                        N = 1
   3.                      Output = 3
|                          Or
hM:1-X,                    X is M - 1
       ?t:1-:Mr:2&         Unify an implicit variable with u(3,N-1,M)
                  :Xr:2&.  Unify Output with u(3,u(3,N-1,M),X)
Fatalize
источник
5

Карамель , 38 байт

(64 ((f->(f,1)),(n f->(3 (n f))),3) 4)

Это синтаксический сахар для выражения 64 лямбда-исчисления (λ m . M (λ f . Λ n . N f 1) (λ n . Λ f . 3 ( n f )) 3) 4, где все числа представлены как церковь цифры .

Андерс Касеорг
источник
(n f->3 (n f))не должно ли это читать n-1?
Дрянная Монахиня
@LeakyNun No. (n f->3 (n f))- это функция для умножения на три в церковных цифрах .
Андерс Касеорг
2
Эта проблема кажется чрезмерно простой в лямбда-исчислении. Зачем?
кошка
3

Пролог (SWIPL), 129/137 байт

g(1,R):-u(3,4,R).
g(L,R):-M is L-1,g(M,P),u(3,P,R).
u(N,1,R):-R is 3**N.
u(1,_,3).
u(N,M,R):-K is N-1,L is M-1,u(K,M,Y),u(Y,L,R).

Чтобы вывести число Грэма, g(64,G).выполните запрос (если нужно подсчитать 8 байтов этого запроса, длина составляет 137 байтов):

?- g(64, G).
ERROR: Out of local stack

Но, как и следовало ожидать, это выходит за пределы стека.

Тест

?- u(3, 2, X).
X = 7625597484987

Возврат приводит к тому, что он выходит за пределы стека:

?- u(3, 2, X).
X = 7625597484987 ;
ERROR: Out of local stack

Ungolfed

Версия без заглавных букв добавляет общую нотацию со стрелкой вверх, а не только для 3, и использует сокращения и проверки, чтобы избежать возврата и неопределенных ситуаций.

% up-arrow notation
u(X, 1, _M, X) :- !.
u(X, N, 1, R) :-
    R is X**N, !.
u(X, N, M, R) :-
    N > 1,
    M > 1,
    N1 is N - 1,
    M1 is M - 1,
    u(X, N1, M, R1),
    u(X, R1, M1, R).

% graham's number
g(1,R) :- u(3, 3, 4, R), !.
g(L,R) :-
    L > 1,
    L1 is L - 1,
    g(L1,G1),
    u(3, G1, R).
SQB
источник
Как вам удалось сделать это, не имея номера 64в вашем коде?
Дрянная Монахиня
@ LeakyNun Я редактировал, чтобы уточнить; лучше?
SQB
Ну, тогда добавьте его в свой код, а также в счетчик байтов.
Дрянная Монахиня
3

C 161 байт

u(int a, int b){if(a==1)return 3;if(b==1)return pow(3,a);return u(u(a-1,b),b-1);}
g(int a){if(a==1)return u(3,4);return u(3,g(a-1));}
main(){printf("%d",g(64));}

РЕДАКТИРОВАТЬ: сохранены 11 байтов путем удаления вкладок и новых строк. РЕДАКТИРОВАТЬ: THX Auhmann сохранил еще один байт и исправил мою программу

thepiercingarrow
источник
1
Вы можете удалить, g(int a){if(a==1)return u(3,4);return g(a-1);}так как он вообще не используется ... Или вы что-то забыли?
августа
@auhmaan К сожалению, я использовал этот номер для тестирования и забыл изменить его обратно. Благодарность!!
thepiercingarrow
Твой return g(a-1)должен быть return u(3,g(a-1)).
Андерс Касеорг
1
Я не знаю, должен ли я дать правильный ответ или просто прокомментировать это, но вы можете довольно легко уменьшить это решение до 114 байт, поняв: новые строки между функциями могут быть опущены. Опущенные типы для всех аргументов устанавливают по умолчанию их значения int (например, K & R). Если такие утверждения можно записать с помощью вложенных троичных операций. Код:u(a,b){return a<2?3:b<2?pow(3,a):u(u(a-1,b),b-1);}g(a){return a<2?u(3,4):u(3,g(a-1));}main(){printf("%d",g(64));}
algmyr
@algmyr вау потрясающе! Вы должны пойти опубликовать свой собственный ответ XD.
thepiercingarrow
2

Mathematica, 59 байт

n_ ±1:=3^n
1 ±m_:=3
n_ ±m_:=((n-1)±m)±(m-1)
Nest[3±#&,4,64]

Использует неопределенный инфиксный оператор, ±который требует только 1 байта при кодировании в ISO 8859-1. См @ Мартин поста для получения дополнительной информации. Функции Mathematica поддерживают сопоставление с образцом для своих аргументов, так что два базовых случая могут быть определены отдельно.

миль
источник
1
С каких это пор Mathematica использовала ISO 8859-1?
Дрянная Монахиня
n_ ±m_:=Nest[#±(m-1)&,3,n]
Дрянная Монахиня
2

C 114 109 байт

Основываясь на ответе @thepiercingarrow ( ссылка ), я немного обдумал ответ. Большая экономия объясняется неправильным набором аргументов по умолчанию при выполнении функций в стиле K & R и заменой операторов if на троичные операторы. Добавлены необязательные переводы строк между функциями для удобства чтения.

Улучшено до 109 благодаря @LeakyNun.

u(a,b){return a<2?3:b<2?pow(3,a):u(u(a-1,b),b-1);}
g(a){return u(3,a<2?4:g(a-1));}
main(){printf("%d",g(64));}
algmyr
источник
g(a){return u(3,a<2?4:g(a-1));}
Дрянная Монахиня
@ LeakyNun Это действительно хороший. Спасибо.
algmyr
1

Python, 85 байт

v=lambda n,m:n*m and v(v(n-1,m)-1,m-1)or 3**-~n
g=lambda n=63:v(2,n and g(n-1)-1or 3)

vФункция определяет ту же функцию, найденные в ответе Дениса : v(n,m) = u(3,n+1,m+1). gФункция нулевого проиндексирована версия традиционной итерации: g(0) = v(2,3), g(n) = v(2,g(n-1)). Таким образом, g(63)это число Грэма. Установив значение по умолчанию для nпараметра gфункции на 63, можно получить требуемый вывод, вызвав g()(без параметров), таким образом, выполняя наши требования для представления функции, которая не требует ввода.

Проверьте v(2,1) = u(3,3,2)и v(4,0) = u(3,5,1)протестируйте онлайн: Python 2 , Python 3

Мего
источник
1
Это сложно проверить, но ваша функция gотключена. Не должно v(2,n-1)быть g(n-1)или что-то подобное?
Деннис
@ Денис Хороший улов. Я исправлю это.
Mego
На самом деле смещение между uи vозначает, что это должно быть g(n-1)-1.
Андерс Касеорг
@AndersKaseorg Я не должен заниматься программированием во время сна. Я должен переучивать это каждые несколько дней.
Mego
@AndersKaseorg В будущем, пожалуйста, не редактируйте материалы других людей, даже если это исправит ошибку в предложенном вами улучшении / исправлении.
Mego
1

Dyalog APL, 41 байт

u←{1=⍺:3⋄1=⍵:3*⍺⋄(⍵∇⍨⍺-1)∇⍵-1}
3u 3u⍣64⊣4

Прецедент:

      3u 2
7625597484987
lstefano
источник
Вы должны быть в состоянии преобразовать 1=⍺:3⋄1=⍵:3*⍺в just 1=⍵:3*⍺( 3=3*1)
Zacharý
1

Рубин, 64 байта

Заимствование из теоретического алгоритма для вычисления числа Грэма .

def f(a,b=3)b<2?3:a<1?3*b:f(a-1,f(a,b-1))end;a=4;64.times{a=f a};p a

Проще говоря, f a = u(3,3,a)и это применяется 64 раза.

Просто Красивое Искусство
источник
Хорошее объяснение того, почему и как работает этот код, было бы неплохо.
Маниш Кунду
Это прямое применение определения числа Грэма.
Просто Красивое Искусство
0

J, 107 байт

u=:4 :0
if.y=1 do.3^x
elseif.x=1 do.3
elseif.1 do.x:(y u~<:x)u<:y
end.
)
(g=:(3 u 4[[)`(3 u$:@<:)@.(1&<))64

Я работаю над преобразованием uв повестку дня, но сейчас это подойдет.

Конор О'Брайен
источник
Нечто подобное u=:3^[`[:(3$:])/[#<:@]@.*@](не проверено)
Leaky Nun
0

F #, 111 108 байт

редактировать

Это использует функцию ниже, чтобы вычислить число Грэма

let rec u=function|b,1->int<|3I**b|1,c->3|b,c->u(u(b-1,c),c-1)
and g=function|1->u(3.,4.)|a->u(3.,g (a-1))
g 63

Вот мой предыдущий ответ, который, ну, не сделал:

Довольно просто. Просто определение uфункции.

let rec u=function|a,b,1->a**b|a,1.,c->a|a,b,c->u(a,u(a,b-1.,c),c-1)

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

u(3.,3.,2)
val it : float = 7.625597485e+12

Если бы я принял значение 3 в качестве значения a, я мог бы сократить его до 60:

let rec u=function|b,1->3.**b|1.,c->3.|b,c->u(u(b-1.,c),c-1)

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

u(3.,2)
val it : float = 7.625597485e+12
asibahi
источник
Задача состоит в том, чтобы написать номер Грэма, а не u. Конечно, вы можете включать любые промежуточные функции, которые вам нужны, например, uс первым аргументом или без него, установленным в 3.
Андерс Касеорг
@AndersKaseorg отредактировал это. Спасибо. Мой предыдущий комментарий, похоже, исчез.
Асибахи
0

R 154 142 128 126 118 байт

u=function(n,b)return(if(n&!b)1 else if(n)u(n-1,u(n,b-1))else 3*b)
g=function(x)return(u(if(x-1)g(x-1)else 4,3))
g(64)

Я использовал определение этой рекурсивной функции из Википедии, потому что по какой-то странной причине предложенная функция не сработала ... или я просто сосу в R гольф.

UPD: побрилось 12 + 14 = 26 байт благодаря совету от Leaky Nun . Предыдущая версия использовала громоздкие и менее эффективные

u=function(n,b)if(n==0)return(3*b)else if(n>0&b==0)return(1)else return(u(n-1,u(n,b-1)))
g=function(x)if(x==1)return(u(4,3))else return(u(g(x-1),3))

UPD: сбрил еще 2 + 6 + 2 байта (опять же, похвала Лики Монахине ) благодаря гениальной замене на «if (x)» вместо «if (x == 0)», потому что x <0 никогда не подается в функция ... верно?

Андрей Костырка
источник
@LeakyNun Спасибо, обновил ответ подтверждением.
Андрей Костырка
Секундочку ... Сегодня мой первый день игры в гольф кода, есть чему поучиться!
Андрей Костырка
Вы приглашены присоединиться к нашему чату .
Утренняя монахиня
Больше игры в гольф, пожалуйста, посмотрите улучшение.
Андрей Костырка
Та-дам, готово, изменил функцию uв том же ключе, что и ваш, gи сохранил еще 6 байтов - потрясающе!
Андрей Костырка
0

PHP, 114 байт

игнорировать разрывы строк; они только для удобства чтения.

function u($n,$m){return$m>1&$n>1?u(u($n-1,$m),$m-1):3**$n;}
function g($x){return u(3,$x>1?g($x-1):4);}
echo g(63);

Второй случай можно интегрировать в первый: для n=1, 3^nравно 3.
Это позволит сэкономить несколько байтов на - насколько я вижу - всех существующих ответах; сэкономил два байта на моем

предыдущая версия, 62 + 43 + 11 = 116 байт

function u($n,$m){return$m>1?$n>1?u(u($n-1,$m),$m-1):3:3**$n;}

Левая ассоциативность троичного языка в PHP требует скобок ... или определенного порядка тестов.
Это сохранило два байта в выражении в скобках.

Вероятно, существует итеративный подход, который может позволить дальнейшую игру в гольф ...
но я не могу сейчас уделить этому время.

Titus
источник
Жаль, что я знал Сесоса или имел время, чтобы изучить его и перевести прямо сейчас
Тит
@Leaky Nun: я разбил его на только петли и сложение. Есть ли способ в Sesos добавить значение одной ячейки к другой?
Тит
@AndersKaseorg: Вы, вероятно, правы ... Я получил пузыри на глазных яблоках, глядя на этот алгоритм. Скоро посмотрю на это снова.
Тит