Euler Projesi 217. Soru

Dengelenmiş Sayılar


⌈x⌉, x'in taban değeri, x'ten büyük en küçük tamsayıyı göstermek üzere, örneğin ⌈π⌉=4 ve ⌈5⌉=5 gibi, eğer k (ondalık) basamaklı bir pozitif tamsayının ilk ⌈k/2⌉ basamağının toplamı son ⌈k/2⌉ basamağının toplamına eşitse bu sayıya dengelenmiş denir.

Bu durumda örneğin, tüm palindromlar dengelenmiştir, 13722 sayısında olduğu gibi.

10ⁿ den küçük tüm dengelenmiş sayıların toplamı T(n) olsun. Böylece T(1)=45, T(2)=540 ve T(5)=334795890 olur.

T(47) mod 3¹⁵ kaçtır?

Cevap: 6273134

C++:

lint Problem() {
    lint ans = 0;
    lint MODE = 1;
    for (int i = 0; i < 15; ++i) {
        MODE *= 3;
    }
    int N = 47;
    int N2 = N / 2;
    int N3 = 10*N2+1;
    vector < lint > v(N3, 0);
    vector < lint > w(N3);
    vector < lint > x(N3, 0);
    v[0] = 0; x[0] = 1;
    ans += 45;
    for (int i = 1; i <= N2; ++i) {
        fill(w.begin(), w.end(), 0);
        vector < lint > y(N3, 0);
        for (int j = 0; j < 10; ++j) {
            for (int k = 0; k < (int) v.size() - j; ++k) {
                lint z = j * Pow(10, i-1, MODE);
                z %= MODE;
                z *= x[k];
                z %= MODE;
                w[k+j] += v[k] + z;
                w[k+j] %= MODE;
                y[k+j] += x[k];
                y[k+j] %= MODE;
            }
        }
        v.swap(w);
        x.swap(y);

        lint ans_t = 0;
        for (int j = 0; j < N3; ++j) {
            lint t = v[j] - w[j] + MODE;
            t %= MODE;
            t *= Pow(10, i, MODE);
            t %= MODE;
            t *= x[j];
            t %= MODE;
            t += v[j] * (x[j] - y[j] + MODE);
            t %= MODE;
            ans += t;
            ans %= MODE;
        }
        for (int j = 0; j < N3; ++j) {
            lint t = v[j] - w[j] + MODE;
            t %= MODE;
            t *= Pow(10, i+1, MODE);
            t %= MODE;
            t *= x[j];
            t %= MODE;
            t += v[j] * (x[j] - y[j] + MODE);
            t %= MODE;
            t *= 10;
            t %= MODE;
            {
                lint z = Pow(10, i, MODE);
                z *= 45;
                z %= MODE;
                z *= x[j];
                z %= MODE;
                z *= x[j] - y[j] + MODE;
                z %= MODE;
                t += z;
            }
            ans += t;
            ans %= MODE;
        }
    }
    return ans;
}

Maple:

countcomp:=proc(n,k)
> option remember;
> local s,i,r,w;
> if k<=0 then return 0 fi;
> if n<0 then return [-1,0] fi;
> if k=1 then if n<=9 then return [n,1] else return [-1,0] fi fi;
> s:=0; w:=0;
> for i from 0 to 9 do
>   r:=countcomp(n-i,k-1);
>   if r[1]<>-1 then s:=s+10*r[1]+r[2]*i fi;
>   w:=w+r[2];
> od;
> [s,w];
> end:

T:=proc(x)
> local q,m,s,r,a,b,s1;
> q:=trunc(x/2);
> m:=x mod 2;
> s:=0;
> for r from 1 to 9*q do
>   b:=countcomp(r,q);
>   a:=b-countcomp(r,q-1);
>   s1:=b[2]*a[1]*10^(m+q)+b[1]*a[2];
>   if a[1]>0 and b[1]>0 then if m=1 then s:=s+10*s1+a[2]*b[2]*45*10^q else s:=s+s1 fi fi;
> od;
> s;
> end:

> f:=x->(add(T(i),i=2..x)+45-4500-450000) mod (3^15);

>t:=time(): f(47); time()-t;
                               6273134
                                0.156

Mathematica:

Project Euler, Problem 217.

In[1]:= (*H[k,s] is number of integers of length <= k summing to s *)
H[x_ /; x <= 0, _] = 0;
H[_, s_ /; s <= 0] = 0;
H[k_, s_] := H[k, s] = Sum[F[j, s], {j, 1, k}]

In[4]:= (*F[k,s] is number f integers length k summing to s *)
F[1, s_ /; 1 <= s <= 9] = 1;
F[1, s_ /; s <= 0 || 9 < s] = 0;
F[x_, s_ /; s < 0] = 0;
F[k_, s_] := F[k, s] = If[0 < s <= 9, 1, 0] + Sum[H[k - 1, s - j], {j, 1, 9}]

In[8]:= (* X[k,s] is the sum of all that are length k, digit sum s *)
X[k_, s_] := 
 X[k, s] = If[1 <= s <= 9, s*10^(k - 1), 0] + 
   Sum[Y[k - 1, s - d] + H[k - 1, s - d]*d*10^(k - 1), {d, 1, 9}]

In[9]:= (* Y[k,s] is the sum of all that have 1 <= length <= k , digit sum s *)
Y[_, s_ /; s <= 0] = 0;
Y[1, s_ /; s <= 0 || 9 < s] = 0;
Y[1, s_ /; 0 <= s <= 9] := s;
Y[k_, s_] := Y[k, s] = Sum[X[j, s], {j, 1, k}]

In[13]:= (* A[k] is total of all length 2k *)
A[k_] := A[k] = Sum[F[k, s] Y[k, s] + H[k, s] X[k, s] 10^k, {s, 1, 9*k}]

In[14]:= (* B[k] is total of all length 2k+1 *)
B[0] = 45;
B[k_] := B[k] = 
  Sum[10 F[k, s] Y[k, s] + 10 H[k, s] X[k, s] 10^(k + 1) + 
    45*10^k F[k, s] H[k, s], {s, 1, 9*k}]

In[16]:= (* total of all length up to length n *)
T[n_] := T[n] = Sum[If[OddQ[j], B[(j - 1)/2], A[j/2]], {j, 1, n}]

In[17]:= Timing[t = T[47]; {t, Mod[t, 3^15]}]

Out[17]= {0.609, {102046816840408378801546174937467503924727519749183651680790418160257\
686837140983269435948860, 6273134}}

Basic:

defdbl a-z

' cnt(i) and ocnt(i) are the number of numbers of n and n-1 digits whose 
' digits total to i. sum(i) and osum(i) are the sums of those numbers.

dim cnt(207), sum(207), ocnt(207), osum(207)

' since all we are doing is addition and multiplication, I'm using mod
' constantly to keep the numbers small
def fnrenorm(n)
    n2 = int(n / arb)
    fnrenorm = n - n2 * arb
end def

arb = 2187# * 6561#       ' 3^15

starttime$ = time$

ocnt(0) = 1
dfac = 1
tau = 45
for n = 1 to 23
    mx = n * 9
    for m = 1 to mx - 9
        ocnt(m) = cnt(m)
        osum(m) = sum(m)
    next
    for m = 1 to mx
        wkc = 0
        wks = 0
        for h = 1 to 9
            if m >= h then
                wkc = wkc + ocnt(m - h)
                wks = wks + fnrenorm(h * dfac * ocnt(m - h)) + osum(m - h)
            end if
        next
        cnt(m) = fnrenorm(cnt(m) + wkc)
        sum(m) = fnrenorm(sum(m) + wks)
    next
'     gosub dump
    dfac = fnrenorm(dfac * 10)

    sig = 0
    for m = 1 to mx
        wks = sum(m) + arb - osum(m)
        wkc = cnt(m) + arb - ocnt(m)
        wkr = fnrenorm(sum(m) * wkc)
        wkl = fnrenorm(wks * cnt(m))
        sig = fnrenorm(sig + wkr + wkl * dfac)
    next
    tau = tau + sig
    print n * 2; sig; tau,
    sig = 0
    for m = 1 to mx
        wks = sum(m) + arb - osum(m)
        wkc = cnt(m) + arb - ocnt(m)
        wkr = fnrenorm(sum(m) * wkc * 10)
        wkl = fnrenorm(wks * cnt(m) * 10)
        sig = fnrenorm(sig + wkr + wkl * dfac * 10)
        wkm = fnrenorm(wkc * cnt(m))
        wkm = fnrenorm(45 * dfac * wkm)
        sig = fnrenorm(sig + wkm)
    next
    tau = fnrenorm(tau + sig)
    print n * 2 + 1; sig; tau

next

print starttime$, time$

Java:

import java.math.*;

public class Problem_217 extends Object
{
 public static BigInteger[][] numPerm, sumPerm, numPermNoZeroStart, sumPermNoZeroStart;
 public static void main(String[] args) {
  long start = System.currentTimeMillis(); 
  final int n = 47;
  fillArrays(n);
  BigInteger tOfN = getTOfN(n);
  
  System.out.println(tOfN.mod(BigInteger.valueOf(3).pow(15)));
  long stop = System.currentTimeMillis();
  System.out.println("Time: " + (stop-start) + "ms");
  
 }
 
 public static void fillArrays(int n) {
  numPerm = new BigInteger[n/2+1][(n/2)*9+1];
  sumPerm = new BigInteger[n/2+1][(n/2)*9+1];
  numPermNoZeroStart = new BigInteger[n/2+1][(n/2)*9+1];
  sumPermNoZeroStart = new BigInteger[n/2+1][(n/2)*9+1];
  for (int i = 0; i < n/2+1; i++) {

   for (int j = 0; j < (n/2)*9+1; j++) {
    numPerm[i][j] = BigInteger.ZERO;
    sumPerm[i][j] = BigInteger.ZERO;
    numPermNoZeroStart[i][j] = BigInteger.ZERO;
    sumPermNoZeroStart[i][j] = BigInteger.ZERO;
    if (i == 0) {
     continue;
    }
    if (j < 10) { 
     if (i == 1) {
      numPerm[i][j] = BigInteger.ONE;
      sumPerm[i][j] = BigInteger.valueOf(j);
      
      if (j != 0) {
       numPermNoZeroStart[i][j] = BigInteger.ONE;
       sumPermNoZeroStart[i][j] = BigInteger.valueOf(j);
      }
     }
    }
    for (int k = 0; k < 10 && k <= j; k++) {
     numPerm[i][j] = numPerm[i][j].add(numPerm[i-1][j-k]);
     sumPerm[i][j] = sumPerm[i][j].add(sumPerm[i-1][j-k]).add(BigInteger.valueOf(k).multiply(BigInteger.TEN.pow(i-1)).multiply(numPerm[i-1][j-k]));
     if (k != 0) {
      numPermNoZeroStart[i][j] = numPermNoZeroStart[i][j].add(numPerm[i-1][j-k]);
      sumPermNoZeroStart[i][j] = sumPermNoZeroStart[i][j].add(sumPerm[i-1][j-k]).add(BigInteger.valueOf(k).multiply(BigInteger.TEN.pow(i-1)).multiply(numPerm[i-1][j-k]));
     }
    }
   }
  }
 }
 

 public static BigInteger getTOfN(int n) {  // any N up to 47
  BigInteger tOfN = BigInteger.ZERO;
  BigInteger tOfi;  // not cumulative, i.e. tOfi when i=5 != T(5), instead it equals T(5)-T(4)
  for (int i = 0; i <= n; i++) {
   if (i == 1) {
    tOfN = BigInteger.valueOf(45);
   }
   if (i % 2 == 0) {
    for (int j = 0; j <= (i/2)*9; j++) {
     tOfi = sumPerm[i/2][j].multiply(numPermNoZeroStart[i/2][j]);
     tOfi = tOfi.add(sumPermNoZeroStart[i/2][j].multiply(numPerm[i/2][j]).multiply(BigInteger.TEN.pow(i/2)));
     tOfN = tOfN.add(tOfi);
    }
   } else {
    for (int j = 0; j <= ((i-1)/2)*9; j++) {
     tOfi = sumPerm[(i-1)/2][j].multiply(numPermNoZeroStart[(i-1)/2][j]);
     
     tOfi = tOfi.add(sumPermNoZeroStart[(i-1)/2][j].multiply(numPerm[(i-1)/2][j]).multiply(BigInteger.TEN.pow((i+1)/2)));
     
     tOfi = tOfi.multiply(BigInteger.valueOf(10));
     
     tOfi = tOfi.add(BigInteger.valueOf(45).multiply(BigInteger.TEN.pow((i-1)/2)).multiply(numPerm[(i-1)/2][j]).multiply(numPermNoZeroStart[(i-1)/2][j]));

     tOfN = tOfN.add(tOfi);
    }
   }
  }
  return tOfN;
 }
 
 
} 

Haskell:

p217_collapse :: (?modulus :: Int) => [(Int, (Int,Int))] -> [(Int, (Int,Int))]
p217_collapse = Map.toList . Map.fromListWith f
    where f (m1, s1) (m2, s2) = (m1 +% m2, s1 +% s2)
p217_attach cts pos d = [(ds + d, (m, s +% pos *% d *% m)) |
                         (ds, (m, s)) <- cts]
p217_right w = foldl f [(0,(1,0))] $ genericTake w $ iterate (10*%) 1
    where f cts pos = p217_collapse $ concatMap (p217_attach cts pos) [0..9]
p217_left w = let lower = p217_right (w-1) in
              p217_collapse $ concatMap (p217_attach lower $ 10^%(w-1)) [1..9]
p217_t n = foldl (+%) 0 [p217_s w | w <- [1..n]]
p217_s 1 = 45
p217_s w | even w    = foldl1 (+%) $ zipWith append l (tail r)
         | otherwise = foldl1 (+%) $ zipWith inject l (tail r)
         where l = p217_left (w//2)
               r = p217_right (w//2)
               pos = 10^%(w `ceildiv` 2)
               pos' = 10^%(w `ceildiv` 2 - 1)
               append (ds1, (m1, s1)) (ds2, (m2, s2))
                  | ds1 == ds2 = (m2 *% pos *% s1) +% (m1 *% s2)
                  | otherwise  = error $ show (ds1, (m1, s1), ds2, (m2, s2))
               inject (ds1, (m1, s1)) (ds2, (m2, s2))
                   | ds1 == ds2 = (10 *% m2 *% s1 *% pos)
                                  +% (45 *% m1 *% m2 *% pos')
                                  +% (s2 *% m1 *% 10)
                   | otherwise  = error $ show (ds1, (m1, s1), ds2, (m2, s2))