This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.

You have an arbitrary number of model kits (which you assemble for

fun and profit). Each kit comes with twenty (20) stickers, two of which

are labeled "0", two are labeled "1", ..., two are labeled "9".

You decide to stick a serial number on each model you assemble starting

with one. What is the first number you cannot stick. You may stockpile

unused numbers on already assembled models, but you may not crack open

a new model to get at its stickers. You complete assembling the current

model before starting the next.

arithmetic/digits/labels.s

The method I used for this problem involved first coming up with a

formula that says how many times a digit has been used in all n models.

n = k*10^i + m for some k,m with 0 <k <10, m < 10^i

f(d,n) = (number of d's used getting to k*10^i from digits 0 to (i-1)) +

(number of d's used by #'s 10^i to n from digit i) + f(d,m)

f(d,n) = i*k*10^(i-1) + (if (d < k) 10^i else if (d == k) m+1 else 0) + f(d,m)

This doesn't count 0's, which should be ok as they are not used as often

as other digits. From the formula, it is clear that f(1,n) is never

less than f(d,n) for 1<d<10.

So I just calculated f(1,n) for various n (with some help from bc).

I quickly discovered that for n = 2*10^15, f(1,n) = 2*n. After further

trials I determined that for n = 1999919999999981, f(1,n) = 2*n + 1.

This appears to be the smallest n with f(1,n) > 2*n.

arithmetic/digits/least.significant/factorial.p

What is the least significant non-zero digit in the decimal expansion of n!?

arithmetic/digits/least.significant/factorial.s

Reduce mod 10 the numbers 2..n and then cancel out the

required factors of 10. The final step then involves

computing 2^i*3^j*7^k mod 10 for suitable i,j and k.

A small program that performs this calculation is appended. Like the

other solutions, it takes O(log n) arithmetic operations.

-kym

===

#include<stdio.h> #include<assert.h> int p[6][4]={ /*2*/ 2, 4, 8, 6, /*3*/ 3, 9, 7, 1, /*4*/ 4, 6, 4, 6, /*5*/ 5, 5, 5, 5, /*6*/ 6, 6, 6, 6, /*7*/ 7, 9, 3, 1, }; main(){ int i; int n; for(n=2;n<1000;n++){ i=lsdfact(n); printf("%d\n",i); } exit(0); } lsdfact(n){ int a[10]; int i; int n5; int tmp; for(i=0;i<=9;i++)a[i]=alpha(i,n); n5=0; /* NOTE: order is important in following */ l5:; while(tmp=a[5]){ /* cancel factors of 5 */ n5+=tmp; a[1]+=(tmp+4)/5; a[3]+=(tmp+3)/5; a[5]=(tmp+2)/5; a[7]+=(tmp+1)/5; a[9]+=(tmp+0)/5; } l10:; if(tmp=a[0]){ a[0]=0; /* cancel all factors of 10 */ for(i=0;i<=9;i++)a[i]+=alpha(i,tmp); } if(a[5]) goto l5; if(a[0]) goto l10; /* n5 == number of 5's cancelled; must now cancel same number of factors of 2 */ i=ipow(2,a[2]+2*a[4]+a[6]+3*a[8]-n5)* ipow(3,a[3]+a[6]+2*a[9])* ipow(7,a[7]); assert(i%10); /* must not be zero */ return i%10; } alpha(d,n){ /* number of decimal numbers in [1,n] ending in digit d */ int tmp; tmp=(n+10-d)/10; if(d==0)tmp--; /* forget 0 */ return tmp; } ipow(x,y){ /* x^y mod 10 */ if(y==0) return 1; if(y==1) return x; return p[x-2][(y-1)%4]; }

arithmetic/digits/least.significant/tower.of.power.p

What are the least significant digits of 9^(8^(7^(6^(5^(4^(3^(2^1))))))) ?

arithmetic/digits/least.significant/tower.of.power.s

9^11 = 9 (mod 100), so we need to find 8^...^1 (mod 10).

8^5 = 8 (mod 10), so we need to find 7^...^1 (mod 4).

7^3 = 7 (mod 4), so we need to find 6^...^1 (mod 2), but

this is clearly 0, so 7^...^1 = 1 (mod 4) ==>

8^...^1 = 8 (mod 10) ==> 9^...^1 = 9^8 (mod 100) = 21 (mod 100).

arithmetic/digits/most.significant/googol.p

What digits does googol! start with?

arithmetic/digits/most.significant/googol.s

I'm not sure how to calculate the first googol of digits of log10(e), but

here's the first 150(approximately) of them...

0.43429448190325182765112891891660508229439700580366656611445378316586464920

8870774729224949338431748318706106744766303733641679287158963906569221064663

We need to deal with the digits immediately after the decimal point in

googol*log10(e), which are .187061

frac[log(googol!)] = frac[halflog2pi + 50 + googol(100-log10(e))]

= frac{halflog2pi + frac[googol(100-log10(e))]}

= frac[.399090 + (1- .187061)]

= .212029

10 ** .212029 = 1.629405

Which means that googol! starts with 1629

arithmetic/digits/most.significant/powers.p

What is the probability that 2^N begins with the digits 603245?

arithmetic/digits/most.significant/powers.s

2^N begins with 603245 iff 603246*10^m > 2^N >= 603245*10^m for some

positive integer m ==> m+log(603246) > N*log(2) >= m+log(603245);

so 2^N begins with 603245 iff frac(log(603246)) > frac(N*log(2))

>= frac(log(603245)). If we are using natural density then N*log(2)

is uniformly distributed mod 1 since log(2) is irrational, hence the

probability is frac(log(603246)) - frac(log(603245)) =

frac(log(603246)-log(603245)) = frac(log(603246/603245)).

A neat observation is that since it is known p_n*c, where p_n is the

nth prime and c is irrational, is uniformly distributed mod 1, we get

the same answer if we replace 2^N with 2^{p_n}.

--

Chris Long, 265 Old York Rd., Bridgewater, NJ 08807-2618

Continue to: