Let σ(n) be the sum of all the divisors of the positive integer n, for example:
σ(10)=1+2+5+10=18.
Define T(N) to be the sum of all numbers n≤N such that when the fraction σ(n)n is written in its lowest form ab, the denominator is a power of 3 i.e. b=3k,k>0.
You are given T(100)=270 and T(10^6)=26089287.
Find T(10^14)
I will try to explain how I solved the problem.
First of all, I define an array as follows in C++.
unsigned long long constarray[30]={4,13,40,121,364,1093,3280,9841,29524,88573,265720,797161,2391484,7174453,21523360,
64570081,193710244,581130733,1743392200,5230176601,
15690529804,47071589413,141214768240,423644304721,1270932914164,3812798742493,
11438396227480,34315188682441,102945566047324};
The first item is 4 and it is the sum of the divisors of 3^1 and it is 1+3.
13= 1+3+3^2
40=1+3+3^2+3^3
The others are calculated using the same method.
One of the items in the array.
11 265720 [(2, 3), (5, 1), (7, 1), (13, 1), (73, 1)]
The factors of 265720 are [(2, 3), (5, 1), (7, 1), (13, 1), (73, 1)], so I should use prime numbers 2,5,7,13,73 and also some other primes to get the exact answer. What are they? 2^4×31, 2^6×127, 2^12×8191…
This is the sum of the array’s item located at 3^11.
7009810733128014.
unsigned long long Calculate(unsigned long long base,unsigned exp){
unsigned long long total=1;
unsigned long long result=1;
for (unsigned j=0;j<exp;j++){
result*=base;
total+=result;
}
return total;
}
The code above calculates the sum of the divisors of the factors of the number.
Unfortunately, I can not put all of the code here. The code is written in both C++ and Python. Absolutely, the C++ version is faster.
The logic behind my algorithm is to find the appropriate prime numbers for the xth exponent of 3.
For example, for x=2, These primes will be used.
unsigned Primes[Itmcount]={2,5,7,13,19,31,37,43,61,73,89,127,151,8191, 131071, 524287};
Some calculated values for 13/(3^2).
The first item is base, the other is exponent.
2 13
7 1
13 1
43 1
127 1
TotalDownResult=36639203328 TotalTopresult 134343745536
2 14
5 1
7 1
19 1
31 1
151 1
TotalDownResult=459010621440 TotalTopresult 1989046026240
2 8
5 1
7 1
19 1
37 1
73 1
TotalDownResult=4138364160 TotalTopresult 17932911360
2 14
7 1
13 1
19 1
31 1
151 1
TotalDownResult=1193427615744 TotalTopresult 4641107394560
2 8
7 1
13 1
19 1
37 1
73 1
TotalDownResult=10759746816 TotalTopresult 41843459840
2 14
5 1
7 1
13 1
19 1
31 1
151 1
TotalDownResult=5967138078720 TotalTopresult 27846644367360
2 8
5 1
7 1
13 1
19 1
37 1
73 1
TotalDownResult=53798734080 TotalTopresult 251060759040
The execution time is about 1250 seconds as seen in the screenshot.
I discovered a faster algorithm using the following data.
2×3
2^2×7
2^3×5
2^4×31
2^5×3^2×7
2^6×127
2^7x3x5x17
2^8×7*73
2^9x3x11x31
2^10x23x89
2^11×3^2x5x7x13
2^12×8191
2^13x3x43x127
2^14x7x31x151
2^15x3x5x17x257
2^16×131071
2^17×3^3x7x19x73
2^18×524287
The powers of 2’s are multipliers of the powers of 3, so they are the denominators.
For example, the sum of divisors of 2^10 is 2^11-1 and that is 23×89-nominator.
Some data is hidden in the following table.
items=[469062957171, X, X, X, X, 540513781756677,
X, X,2946130223694300, X, X, X,
X, X, X, X, 5343105541558284, X,
X, 235382354558307, X, 162491126655402, X, 151099802017335,
63546645708225, 172846876326372, 228767924549610, 22876792454961, 68630377364883]
The answer of the problem is the sum value of the array above. For instance, the first item in items-469062957171- is the sum value when one of the factor of the denominator is exactly 3^1, whereas the last item-68630377364883- is the sum when the denominator has a factor 3^29.
^ means the power or the exponent value.
Algoprogen 