Herhangi Matematiksel Şeyler: Euler Projesi 282. Soru

Ackermann fonksiyonu

Negatif olmayan m, n tamsayıları için Ackermann fonksiyonu aşağıdaki gibi tanımlanır:

A (m, n) = {\begin{cases} n + 1 & if m = 0 \\ A (m - 1, 1) & if m > 0 and n = 0 \\ A (m - 1, A (m, n - 1)) & if m > 0 and n > 0 \end{cases}

\begin{array}{ll}  \end{array}

Örneğin $A(1,0)=2, A(2,2)=7$ ve $A(3,4)=125$.

$\sum_{n=0}^{6}A(n,n)$ değerini bulup cevabı mod 14⁸ olarak veriniz. Cevap: 1098988351

Python:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import zm
from zdecs import timing

mod = 14**8

def a(n):
    if n == 0:
        return n+1
    elif n == 1:
        return n+2
    elif n == 2:
        return 2*n+3
    elif n == 3:
        return (2**(n+3) - 3)
    elif n == 4:
        return zm.tetration_mod(2, 7, mod) - 3
    else:
        return zm.tetration_mod(2, 10**3, mod) - 3

@timing
def p282():
    s = sum(a(i) for i in range(7))
    print('Solution: {0}'.format(s%mod))

p282()

'''
Solution: 1098988351
p282 took 0.001910 s
'''
  
Haskell:
import Number (factors)
import Modulo (powMod)
import Data.List (group, genericLength)

phi :: Integer -> Integer
phi 1 = 1
phi n = product.map f.group.factors $ n
    where f ps@(p:_) = let m = length ps
                       in p ^ (m-1) * (p-1)

tower :: (Num t, Integral a) => a -> t -> a
tower a 0 = 1
tower a n = a ^ (tower a $ n - 1)

towerMod :: (Num a, Ord a) => Integer -> a -> Integer -> Integer
towerMod _ _ 1 = 0
towerMod a n m 
    | n < 4 = mod (tower a n) m
    | otherwise = powMod a x m
    where x = until (p<) (+ phi q).towerMod a (n-1) $ phi q
          (p, q) = strip a m

strip :: (Num t1, Integral t) => t -> t -> (t1, t)
strip a n = f (0, n)
    where f (c, m) | mod m a == 0 = f (c+1, div m a)
                   | otherwise    = (c, m)

ack :: (Num t) => t -> Integer -> Integer
ack 0 _ = 1
ack 1 m = 3
ack 2 m = 7
ack 3 m = powMod 2 6 m - 3
ack 4 m = towerMod 2 7 m - 3
ack n m = towerMod 2 u m - 3
    where u = genericLength.takeWhile (1/=).iterate (phi.snd.strip 2) $ m

main :: IO ()
main = print $ sum [ack n m| n <- [0..6]] `mod` m
    where m = 14 ^ 8
                                  
C/C++:
#include <iostream>
#include <vector>
using namespace std;

#define lim 1475789056
#define lint __int64
#define gr 25000000

lint int rek(int A, int mod){
     if (A==1) return 2;
     if (mod==2) return 0;
     lint m=1, pom, suma;
     {
        vector <int> niz(gr,0);
        for (int i=1;i<=gr;i++) {
            m=(m*2)%mod;
            if (m<gr&&niz[m]) {pom=i-niz[m]; break;}
            if (m<gr) niz[m]=i;
        }
     }
     suma=rek(A-1,pom), m=1;
     for (int i=1;i<=suma;i++) m=(m*2)%mod;
     return m;
}

int main(){
    cout<<(rek(7,lim)+2*rek(10,lim)-9+1+3+7+61)%lim<<endl;;
    return 0;
}

Herhangi Matematiksel Şeyler

Sayfalar

26 Eylül 2020

Euler Projesi 282. Soru