modular arithmetic on 1^1+2^2+3^3+...+n^n
by fungarwai, Dec 13, 2021, 1:45 PM
To find the modular residue ,
the main idea is rewriting as
While is enough small, would be simply zero.
has to be calculated manually. Make it as short as it can.
Here is the main problem.
Proof
(Refer Summation with polynomial)
Note 1
Note 2
Note 3
Proof
Example
Python program for general cases
input values for n, m to get
input values for N, p, s to get for
the main idea is rewriting as
While is enough small, would be simply zero.
has to be calculated manually. Make it as short as it can.
Here is the main problem.
Proof
(Refer Summation with polynomial)
Note 1
Note 2
Note 3
By Kummer's theorem, is equal to the number of carries
when is added to in base p
There are at least number of carries when
Otherwise,
when is added to in base p
There are at least number of carries when
Otherwise,
Proof
Example
Summation
Find the units digit of
program check
program check
A spin off an old USAMTS
Determine the rightmost three digits of the number
program check
program check
(Refer Application of elementary operations in Euclidean algorithm)
Find the units digit of
program check
N = 1010 p = 2 s = 1 for r in range(1,p): sum=0;m=p**s; for k in range(1,N+1): P=1 for t in range(1,p*(k-1)+r+1): P=(P*(p*(k-1)+r)) % m sum=(sum+P) % m print(sum, "when r=",r)
program check
N = 404 p = 5 s = 1 for r in range(1,p): sum=0;m=p**s; for k in range(1,N+1): P=1 for t in range(1,p*(k-1)+r+1): P=(P*(p*(k-1)+r)) % m sum=(sum+P) % m print(sum, "when r=",r)
sum=0;n=2021;m=10; for k in range(1,n+1): p=1 for t in range(1,k+1): p=(p*k) % m sum=(sum+p) % m print(sum)
A spin off an old USAMTS
Determine the rightmost three digits of the number
program check
N = 500 p = 2 s = 3 for r in range(1,p): sum=0;m=p**s; for k in range(1,N+1): P=1 for t in range(1,p*(k-1)+r+1): P=(P*(p*(k-1)+r)) % m sum=(sum+P) % m print(sum, "when r=",r)
program check
N = 200 p = 5 s = 3 for r in range(1,p): sum=0;m=p**s; for k in range(1,N+1): P=1 for t in range(1,p*(k-1)+r+1): P=(P*(p*(k-1)+r)) % m sum=(sum+P) % m print(sum, "when r=",r)
(Refer Application of elementary operations in Euclidean algorithm)
sum=0;n=1000;m=1000; for k in range(1,n+1): p=1 for t in range(1,k+1): p=(p*k) % m sum=(sum+p) % m print(sum)
Python program for general cases
input values for n, m to get
n = int(input("n=")) m = int(input("m=")) sum=0; for k in range(1,n+1): p=1 for t in range(1,k+1): p=(p*k) % m sum=(sum+p) % m print(sum)
input values for N, p, s to get for
N = int(input("N=")) p = int(input("p=")) s = int(input("s=")) sum=0;m=p**s; for r in range(1,p): for k in range(1,N+1): P=1 for t in range(1,p*(k-1)+r+1): P=(P*(p*(k-1)+r)) % m sum=(sum+P) % m print(sum, "when r=",r)
This post has been edited 2 times. Last edited by fungarwai, Dec 14, 2021, 12:15 PM