66 arithmetic/digits/labels.p
Description
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.
66 arithmetic/digits/labels.p
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:
My Books
