Re: Part I solved ! Any takers for the 2nd half ? :-) Message #44 Posted by PeterP on 16 Feb 2007, 12:50 a.m., in response to message #43 by PeterP
OKay, I give up. I'm not smart enough for a smart way, so here is a rather brute force way for my trusty old 41, with the usual help of Mr. Angel Martin.
The concept is rather straight forward: It calculates the prime-factor construction (? don't know the right english term) of n!, using the nifty little routine we developped in part 1 (where we used it for 5 only, now we use it for all primes <= n).
It then makes use of four obvious facts: 1) it removes all the 2*5 pairs, as they just give 0; 2) the last digit of p^k is identikal to the last digit of p^(k mod 4); 3)all primes end either 1,3,7 or 9 and have the same effect as 3,7,9 and hence we sum them all up in the same reg 0p and use the nifty mod 4 factor to keep all numbers small and neat and lastly 4) we do not need to calculate the powers of all primes which end with a 1, they do not affect the last digit of n!. This check (done at the start of Lbl 02) does not help with the small n, but becomes handy at the larger n, where we do get powers of 11,31, etc...
Anyway, the below program is long and takes it sweet little time on the 41 for large n (about 4min for 2007!, it scales with about sqrt(n) or less for large n. Far from the 'almost instantaneous of Valentin...) but it has the advantage that a) I was able to figure it myself and b)it works. Both of which are no small feats for little ole' me...
Anyway, thanks for Valentin for great fun and I write some comments after the listing about where I got stuck with counting all the factors of 5 for large n while trying to do this a smart way...
Lbl LSSMC (for Little Short and Sweet Mathc Challenge)
CLRG (just some prep work, storing of numbers etc)
CLA
Sto 11 (this is n)
Sto 12 (this will hold the first prime to test, either n or n-1)
2
Sto 00 (store it for speed purposes, digits are reaaaal slow for 41)
Mod
X=1?
GTO 00
1
St- 12
Lbl 00
10
Sto 04 (store for speed purposes)
Rcl 12
Lbl 01 (go down from n and find all primes)
Prime? (God, I love you Angel...)
GTO 02
Last X
Rcl 00 (reg 00 is the number 2)
-
GTO 01
Lbl 02
Sto 10
Rcl 04 (check if the prime ends in 1, if so, ignore)
Mod
X=1?
GTO 05
CLA (this clears Reg M fastly...)
Rcl 11
Lbl 03 (this routine should be familiar...)
Rcl 10 (reg 10 is the current prime factor)
/
Int
Sto+ M
X>0?
GTO 03
Rcl 10
Rcl 04 (reg 04 is the number 10)
Mod
Sto+ Ind Y
Lbl 05 (we land here if we had found a prime ending in 1, which we
can ignore)
Rcl 10
Rcl 00 (reg 00 is the number 2)
-
X=1?
GTO E (pfhh, we are done...)
GTO 01
Lbl E
Tone 9 (almost done)
CLA
Rcl 11
Lbl 04 (this gets the power of 2)
Rcl 00
/
Int
Sto+ M
X>0?
GTO 04
Rcl M
Rcl 05 (subtract the powers of 5)
-
4
Mod
X=0?
4
Rcl 00
X<>Y
y^x
Sto 01 (01 keeps the relevant digits)
Rcl 03 (this, Lbl 07 and Lbl 09 collect the powers of all primes
ending in 3,7 and 9)
x=0?
GTO 07
4
Mod
x=0?
4
3
x<>y
y^x
Sto* 01
Lbl 07
Rcl 07
X=0?
GTO 09
4
Mod
X=0?
4
7
x<>y
y^x
Sto* 01
Lbl 09
Rcl 09
x=0?
GTO 10
4
Mod
x=0?
4
9
x<>y
y^x
Sto*01
Lbl 10 (Horray!!)
Rcl 01
Rcl 04
Mod
Beep
Stop
Here is where i got stuck trying to find a smarter way: basically onbly the last digit of all 1,2,3,...n matter for the last digit of n! (lets call it ld(n!)). so one could simply count how often one gets the sequence 1*2*3*4*5*6*7*8*9, lets call that X. Knowing that 9! gives a last digit of 8 (after removing the 2*5 for the zero), the ld(n!) = ld(8^(X mod 4)). Well, almost, but not quite. The nasty thing is that the numbers ending with 5 in n (e.g. 15,25,35 for n=36) leave some remnants after the 5 is paired off with a two. So the 15 leaves a 3 (from 3*5), the 25 leaves a 5 (from 5*5) and 35 leaves a 7 (from 5*7). One has to multiply the 8^(Xmod4) with all those remnants to get the right number. And then there is additionally the factors from the full 10's (2 from the 20 and 3 from the 30). Things get really ugly when n>100, as you get another nasty 5 from the 50, that you could pair off with the 2 from the 20 to ignore, and be left with the 3*4*6*7*8*9 which gives a last digit of 8 again. So you have to count those again. Somewhere just about now my brain gave up on to keep track of all the 5's floating around that are not paired off with a 2. Yet I'm sure there must be ab even smarter way. Angel provides a nifty function that can move any number into any base. Maybe moving n into base 5 can help to avoid the above mentioned problems of keeping track of them, but it is now to late for me to think about this.
|