clearvars,clc
%all same base
p5=sym(1); base=sym(1);
goal=(sym(7)^22)
while p5<=(sym(7)^22)/2
base=base+1;
p5=base^5;
if mod(goal,p5)==0
disp([p5 goal/p5 base])
end
end
produces the following (with annotations added):
goal =
3909821048582988049
[16807, 232630513987207, 7]
[282475249, 13841287201, 49]
[4747561509943, 823543, 343]
[79792266297612001, 49, 2401]
This shows that 49*2401^5 will sum up to 7^22, which is 3909821048582988049, so if the fifth powers were to need to be equal, there'd need to be 49 at minimum.
But the puzzle doesnt need to have equal bases, so let's try a greedy algorithm. The largest base for powering to the fifth power is 5229, so let's start there. Being a greedy algorithm means it goes down the list of powers until it finds one that will fit within what's left from the higher powers, and it takes as many as it finds,
%greedy algorithm
remain=goal; tot=0;
b=5229
p5=sym(b)^5
while remain>0
q=floor(remain/p5);
tot=tot+q; disp([b q])
remain=remain-q*p5;
b=floor(eval(remain^(1/5)));
p5=sym(b)^5;
end
tot
b =
5229
p5 =
3909247878475417149
[5229, 1]
[894, 1]
[291, 1]
[109, 1]
[49, 1]
[28, 1]
[17, 1]
[12, 1]
[9, 1]
[6, 1]
[5, 1]
[3, 1]
[2, 5]
[1, 17]
tot =
34
The above starts with the highest possible power, 5229. When raised to the fifth power it gives 3909247878475417149 and only one will fit.
5^5229
+ 5^894
+ 5^291
+ 5^109
+ 5^49
+ 5^28
+ 5^17
+ 5^12
+ 5^9
+ 5^6
+ 5^5
+ 5^3
+ 5^2 * 5
+ 5^1 * 17
This adds up to 7^22.
This lowers the value of n to 34.
%greedy with different starting point
remain=goal; tot=0;
b=4000 %b=5229;
p5=sym(b)^5
while remain>0
q=floor(remain/p5);
tot=tot+q; disp([b q])
remain=remain-q*p5;
b=floor(eval(remain^(1/5)));
p5=sym(b)^5;
end
tot
b =
4000
p5 =
1024000000000000000
[4000, 3]
[3842, 1]
[931, 1]
[320, 1]
[115, 1]
[58, 1]
[34, 1]
[19, 1]
[12, 1]
[6, 1]
[4, 2]
[3, 1]
[2, 3]
[1, 5]
tot =
23
The explanation of this is as above. This time n has been lowered to 23.
The best that I could do experimentally is n = 20:
goal =
3909821048582988049
b =
3450
p5 =
488759796562500000
[3450, 7]
[3449, 1]
[852, 1]
[278, 1]
[76, 1]
[41, 1]
[21, 1]
[14, 1]
[9, 1]
[8, 1]
[4, 2]
[2, 1]
[1, 1]
tot =
20
But because this is a greedy algorithm you see all those powers of 5 being used only once. Just as lowering the starting value can aid in lowering the value of n, perhaps a non-greedy algorithm would temporarily forgo a power that will fit so that a lower power can achieve a better fit and lead to a lower n.
This would entail a recursive algorithm that would go through all the lower powers at each level, to see what leads to the lowest n. However, there are thousand to try at each level until you get near the end.
|
|
Posted by Charlie
on 2023-04-13 13:57:54 |
Best greedy algorithm I could find is nowhere near as good as Larry's algorithm
