Herhangi Matematiksel Şeyler: Euler Projesi 254. Soru

Basamak Faktöriyellerinin Toplamı

n sayısının rakamlarının faktöriyelleri toplamı f(n) ile gösterilsin. Örneğin f(342)=3!+4!+2!=32.

f(n) sayısının rakamlarının faktöriyelleri toplamı da sf(n) ile gösterilsin. sf(342)=3!+2!=5 gibi.

sf(n)=i olacak şekilde en küçük n pozitif tam sayı g(i) ile tanımlansın. Yani sf(342)=5 ve yine sf(25)=5 olduğundan g(5)=25 olduğu onaylanabilir.

g(i) sayısının basamakları toplamı ise sg(i) ile verilsin. Böylece sg(5)=2+5=7 olur.

Dahası g(20)=267 ve $1\le i\le 20$ için $\sum$sg(i)=156 olduğu gösterilebilir.

$1\le i\le 150$ için $\sum$sg(i) kaçtır?

Cevap: 8184523820510

C/C++:
#include <iostream>

#define TO 150
#define BFLIMIT 72

const int factorial[10]={1,1,2,6,24,120,720,5040,40320,362880};

int len, slen, bestlen, target;
long long sgi, val;

int fillin(int n){
 slen=0;
 int res=0;
 for(int i=8;i>0;--i){
  int ni=n/factorial[i];
  slen+=ni;
  res+=i*ni;
  n-=ni*factorial[i];
 }
 return res;
}

int ksum[1000], kmdig[1000];
int digitsum(int of=val){
 int n=of/1000;
 int ret=ksum[of-n*1000];
 
 while(n){
  int tmp=n;
  n/=1000;
  ret+=ksum[tmp-n*1000];
 }
 return ret;
}

int maxdigitsum(int n){
 ++n; //Special handling of number in form x999...
 int res=-1; //We need to decrease top digit to gain max sum
 while(n>=1000){
  res+=9*3;
  n/=1000;
 }
 return res+kmdig[n];
}

//~60% of program time here
bool can_make(int i,int lower,int add){
 add=factorial[add]-1;
 bool borrow=false;
 for(int d=0;;++d){
  int a=add%10;
  add/=10;
  int b=lower%10;
  lower/=10;
  if(borrow){
   if(a){
    --a;
    borrow=false;
   }
   else a=9;
  }
  if(a+b>=9){}
  else if(add){
   borrow=true;
  }
  else{
   return (i<=d*9+a+b+digitsum(lower)); //Ignore lower bound
  }
 }
}

//Bruteforce functions
int try_vec[10], best_vec[9];
template<int N>
void bf_test(){
 int fn=factorial[N];
 for(int i=0;i<=N;++i){
  if(i){
   val+=fn;
   ++len;
   if(len>bestlen)continue; //Quit loop (but maintain 'val')
  }
  //Check if value is possible to get to
  // (but skip check for N=1,2 for efficiency and correctness)
  if(N>2){
   if(!can_make(target,val,N))continue;
  }
  try_vec[N]=i;
  bf_test<N-1>();
 }
 val-=N*fn;
 len-=N;
}

template<>
void bf_test<9>(){
 val=0;
 len=0;
 int fn=factorial[9];
 for(int i=0;i<=bestlen;++i){
  if(i){
   val+=fn;
   ++len;
  }
  //Check if value is possible to get to
  if(maxdigitsum((i+1)*fn-1)<target)continue;
  try_vec[9]=i;
  bf_test<8>();
 }
}

template<>
void bf_test<0>(){
 if(digitsum()!=target)return;
 if(len==bestlen){
  for(int i=1;i<9;++i){
   if(best_vec[i]>try_vec[i])return;
   if(best_vec[i]<try_vec[i])break;
  }
 }
 bestlen=len;
 for(int i=1;i<9;++i){
  best_vec[i]=try_vec[i];
 }
 sgi=0;
 for(int i=1;i<10;++i){
  sgi+=try_vec[i]*i;
 }
}

int main(){
 for(int a=0;a<10;++a)for(int b=0;b<10;++b)for(int c=0;c<10;++c)
  ksum[a+10*(b+10*c)]=a+b+c;
 for(int i=0;i<1000;++i){
  int n=i, res=0;
  while(n>=10){
   res+=9;
   n/=10;
  }
  kmdig[i]=res+n;
 }
 long long adds=1, si=0;
 long long res=0;
 int fronts=0;
 
 for(int i=1;i<=TO;++i){
  
  //Update si
  if(++fronts>=10){
   fronts=1;
   adds*=10;
  }
  si+=adds;
  
  //Calculate sg(i)
  sgi=si/factorial[9]*9+fillin(si%factorial[9]);
  
  //Calculate lower values separately, since sgi might be wrong
  
  do{
   //Only bruteforce when needed
   if(i>=BFLIMIT)break;
   int pdif=adds/factorial[8];
   if(fronts!=9)pdif/=10;
   if(slen<pdif)break;
   
   //Current bounds
   bestlen=si/factorial[9]+slen; //Maximum number of nines (<52, it seems)
   for(int j=1;j<9;++j){
    best_vec[j]=0;
   }
   
   //Run bruteforce
   target=i;
   bf_test<9>();
  }while(0);
  res+=sgi;
 }
 std::cout << res << std::endl;
 return 0;
}

PYTHON:
def factorial(n):
    if n == 0:
        return 1
    else:
        return n*factorial(n-1)

fac = [factorial(i) for i in range(10)]

def partitions(n,d = None,start = 1):
    # generates numbers that add up to n, in numerical order
    # d = number of digits, or any number if left out
    # start makes first digit start at 1 instead of 0.
    if d == None:
        i = 0
        sub = None
        while True:
            if sub == None:
                i += 1
                sub_gen = partitions(n,i,start=1)
            else:
                yield sub
            sub = sub_gen.next()
    elif d == 0:
        yield ''
        while True:
            yield None
    else:
        start = max(start,n-(d-1)*9)
        stop = min(9,n)
        for i in range(start,stop+1):
            sub_gen = partitions(n-i,d-1,start=0)
            while True:
                sub = sub_gen.next()
                if sub == None:
                    break
                yield str(i) + sub
        yield None

def f(n):
    return sum(fac[int(d)] for d in str(n))

def sf(n):
    return sum(int(d) for d in str(f(n)))

def g(i):
    n = 1
    while sf(str(n)) != i:
        n += 1
    return n

def reverse(n):
    # finds number for which the factorials of digits add up to to n.
    # represents as a list: [-totaldigits, ones, twos, threes...]
    # i.e., 1111223499 is [-10,4,2,1,1,0,0,0,0,2]
    # this guarantees that these representations are ordered properly
    result = []
    for i in range(9,0,-1):
        m,n = divmod(n,fac[i])
        result.append(m)
    result.append(-sum(result))
    return result[::-1]

def g2(i):
    # try each number whose digits add up to i
    part = partitions(i)
    best = None # works because any list > None
    while True:
        n = part.next()
        x = reverse(int(n))
        if x > best: 
            best = x
        if x[9] > -best[0]:
            # more nines in x than all digits in best.
            return best
            
def sg(i):
    if i <= 40:
        return sum(int(d) for d in str(g(i)))
    else:
        l = g2(i)
        return sum(l[j]*j for j in range(1,10))

print sum(sg(x) for x in range(1,151))

HASKELL:
import Data.List (foldl', genericReplicate, mapAccumR, find)
import Data.Char (digitToInt, intToDigit)

fact, greedy :: Integral a => a -> Integer
fact n = product [1..toInteger n]
greedy n = foldl' add 0 $ mod n 9 : genericReplicate (div n 9) 9
    where add a b = a*10+toInteger b

powRadic :: Integer -> [Integer]
powRadic x = snd.mapAccumR (swapf divMod) x .map fact $ [1..9]
    where swapf f x y = let (a,b) = f x y in (b,a)

gen :: Integer -> [Integer]
gen n  = gpart n 1
    where gpart n 9 = [n * fact 9]
          gpart n k = concat [map (l * fact k +) $ gpart (n-l) (k+1) | l <- reverse [0..min n k]]

search :: Int -> [Integer]
search n = spart 1
    where spart k = maybe (spart $ k+1) powRadic.find ((n==).sd).gen $ k
          sd = sum.map digitToInt.show

divid :: Int -> Int -> [[Int]]
divid s (d+1) = concat [map (k:) $ dpart (s-k) d | k <- [1..9]]
    where dpart 0 0 = [[]]
          dpart _ 0 = []
          dpart s d = concat [ map (k:) $ dpart (s-k) (d-1) | k <- [0..min 9 s]]

searchMid :: Int -> [Integer]
searchMid n = spart.map (powRadic.read.map intToDigit).concatMap (divid n) $ [div (n+8) 9..]
    where spart (x:xs) = spart' x xs
          spart' x (y:ys) | sum x < last y = x
                          | gt x y         = spart' y ys
                          | otherwise      = spart' x ys
          gt x y = sum x > sum y || sum x == sum y && x < y

p254 :: Int -> Integer
p254 n = foldl' add 0.map g $ [1..n]
    where add s = (s+).sum.zipWith (*) [1..9]
          g x | x < 45    = search x
              | x < 63    = searchMid x
              | otherwise = powRadic.greedy $ x

main :: IO ()
main = print $ p254 150

JAVA:
public static long[] Fa = {1L,1L,2L,6L,24L,120L,720L,5040L,40320L,362880L},SG , SGd;
public static long[][] inddiv;
public static int T = 0;
    public static void artymus(){
        Date d1 = new Date();
        SG = new long[151];
        SGd = new long[151];
        inddiv = new long[151][10];
        long s = 0;       
     for(long I = 1; I < 10000000; I++){
           int z = (int) sumdigf(I);
           if(SG[z] == 0){SG[z] = su(I);}
            }
        int IN = 1;
      // for(int i = 1; i < 21; i++){s += SG[i];}
     while(SG[IN] > 0){ s += SG[IN]; IN++;}
    System.out.println(IN);
        for(int i = IN+0; i <= 150; i++){
            System.out.println(i);
            if(SG[i] == 0){
            T = i+0;
            if(i < 82){
            int L = Math.max(1,(i+8)/9);
            int H = Math.max((i+8)/9, Math.min(8,2*(1+(i+8)/9)));
            for(int l = L; l <= H; l++){
                sg(i+0,l+0,"");
                }
            }
            else{SG[i] = sf(greed(i));}
            }
            s += SG[i];
            }
         
         System.out.println(s);
       Date d2 = new Date();
    System.out.println(d2.getTime() - d1.getTime());
       
        }
    public static long greed(int n){
        String t = "";
        while(n > 9){t += 9;  n -= 9; }
        return Long.parseLong(n+t);
        }
    public static void sg(int s, int dig, String st){
        if(dig == 0){
            if(!st.substring(0,1).equals("0")){
                long ST = Long.parseLong(st);
                if(SG[T] == 0 || Dt(ST) < SGd[T]){
                    SG[T] = sf(ST); SGd[T] = Dt(ST); inddiv[T] =  distrib(ST);
                    }
                else if(Dt(ST) == SGd[T]){
                    boolean R = true;
                    long[] STdist = distrib(ST);
                    for(int i = 1; i < 9; i++){
                        if(STdist[i] > inddiv[T][i]){R = false; break;}
                        if(STdist[i] < inddiv[T][i]){break;}
                        }
                        if(!R){
                            SG[T] = sf(ST); inddiv[T] = STdist;}
                    }
            }
            }
        else{
            for(int m = Math.max(0,s-9*(dig-1)); m <= Math.min(s,9); m++){
                sg(s-m,dig-1,st+m);
                }
            
            }
        }
    public static long Dt(long S){
        long p = 0;
        for(int i = 9; i > 0; i--){
            p += (S/Fa[i]);
            S = S % Fa[i];
            }
        return p;
        }
    public static long[] distrib(long S){
        long[] dib = new long[10];
        for(int i = 9; i > 0; i--){
           dib[i] = (S/Fa[i]);
            S = S % Fa[i];
            }
        return dib;
        }
    public static long sumdigf(long x){
        long s = 0;
        while(x > 0){
            s += Fa[(int)(x % 10)];
            x /= 10;
            }
        return su(s);
        }
    public static long sf(long S){
        long p = 0;
        for(int i = 9; i > 0; i--){
            p += (long) i * (S/Fa[i]);
            S = S % Fa[i];
            }
        return p;
        }
    public static int su(long x){
        int S = 0;
        while(x > 0){S += x % 10; x /= 10;}
        return S;
        }

PASCAL:
const maxx=150;

var i1,i2,i3,i4,i5,i6,i7,i8,q,q2:longint;
var nana,cif,xxt,lcis,iio,sufa,xsufa:int64;
var cis,sufas,ts:string;
var popro:int64;

var tcif,mnana:int64;
var ipp:longint;
var weref:boolean;

var itogo:int64;

var nas:array[1..maxx] of boolean;
var pods:array[1..maxx] of int64;
var leng:array[1..maxx] of int64;
var fact:array[1..9] of int64;

procedure poxsufa;
var tll:int64;
begin

tll:=i1+2*i2+3*i3+4*i4+5*i5+6*i6+7*i7+8*i8;
        tll:=tll+(popro-lcis)*9; {append 9's}
pods[xsufa]:=tll;

end;

begin
weref:=false;
nana:=maxx;
fact[1]:=1;fact[2]:=2;fact[3]:=6;fact[4]:=24;fact[5]:=120;fact[6]:=720;
fact[7]:=fact[6]*7;
fact[8]:=fact[7]*8;
fact[9]:=fact[8]*9;
for q:=1 to maxx do begin nas[q]:=false; pods[q]:=0; leng[q]:=0; end;
itogo:=0;

popro:=1;
repeat

for i1:=0 to 1 do
for i2:=0 to 2 do
for i3:=0 to 3 do
for i4:=0 to 4 do
for i5:=0 to 5 do
for i6:=0 to 6 do
for i7:=0 to 7 do
for i8:=0 to 8 do
        begin

lcis:=i1+i2+i3+i4+i5+i6+i7+i8;

if lcis<=popro then
                begin

sufa:=i1*fact[1]+i2*fact[2]+i3*fact[3]+i4*fact[4];
                sufa:=sufa+i5*fact[5]+i6*fact[6]+i7*fact[7]+i8*fact[8];
                sufa:=sufa+(popro-lcis)*fact[9]; {append 9's}

xsufa:=0;
                xxt:=sufa;
                repeat
                xsufa:=xsufa+(xxt mod 10);
                xxt:=trunc(xxt/10);
                until xxt=0;

if (nas[xsufa]=false) and (xsufa<=maxx) then
                        begin
                        nas[xsufa]:=true;
                        leng[xsufa]:=popro;

poxsufa;

dec(nana);
                        writeln(' Yields F:',sufa,' Yields SF:',xsufa, ' At level: ',popro, ' Remains: ',nana);
                        weref:=true;
                        end
                        else
                        begin
                         if leng[xsufa]=popro then
                                begin
                                Writeln (' BETTER F:',sufa,' BETTER SF:',xsufa, ' At level: ',popro,' Remains: ',nana);
                                weref:=true;
                                poxsufa;
                                end;
                        end;
end;
end;

if (nana>85) then inc(popro) else
   if not(weref) then inc(popro) else
        begin
        weref:=false;
        mnana:=maxx-nana+1;
        tcif:=mnana mod 9;
        for ipp:=1 to trunc(mnana/9) do tcif:=tcif*10+9;
        tcif:=trunc(tcif/fact[9]);
        popro:=tcif;
        end;
writeln ('LEVEL ',popro, ' BEGINNING! (REMAINS ',nana,')');

until nana=0;

itogo:=0;
for q2:=1 to maxx do itogo:=itogo+pods[q2];
        writeln ('Itogo at last: ',itogo);

end.

Herhangi Matematiksel Şeyler

Sayfalar

10 Kasım 2018

Euler Projesi 254. Soru