Smallest power of 6 whose decimal expansion contains n: Difference between revisions
Smallest power of 6 whose decimal expansion contains n (view source)
Revision as of 19:13, 11 June 2021
, 2 years agoAdded Algol W
(Added Algol W) |
|||
Line 86:
21: 6^3 216
</pre>
=={{header|ALGOL W}}==
Algol W doesn't have integers larger than 32 bits, however we can handle the required numbers with arrays of digits.
<lang algolw>begin % find the smallest power of 6 that contains n for 0 <= n <= 21 %
% we assume that powers of 6 upto 6^32 will be sufficient %
% as Algol W does not have integers longer than 32 bits, the powers %
% will be held in an array where each element is a single digit of the %
% power, the least significant digit of 6^n is in powers( n, 1 ) %
integer array powers ( 0 :: 32, 1 :: 32 ); % the powers %
integer array digits ( 0 :: 32 ); % the number of digits in each power %
integer array lowest ( 0 :: 21 ); % the lowest power containing the idx %
for n := 0 until 21 do lowest( n ) := -1;
% 6^0 = 1, which is the lowest power containing 1 %
lowest( 1 ) := 0;
powers( 0, 1 ) := 1;
for d := 2 until 32 do powers( 0, d ) := 0;
digits( 0 ) := 1;
% calculate the remaining powers and find the numbers 0..21 %
for p := 1 until 32 do begin
integer carry, dPos, dMax;
dPos := 1;
dMax := digits( p - 1 );
carry := 0;
% compute the power p and find the single digit numbers %
while dPos <= dMax do begin
integer d;
d := carry + ( powers( p - 1, dPos ) * 6 );
carry := d div 10;
d := d rem 10;
if lowest( d ) < 0 then lowest( d ) := p;
powers( p, dPos ) := d;
dPos := dPos + 1
end while_dPos_le_dMax ;
if carry = 0
then digits( p ) := dMax
else begin
% the power p has one more digit than the previous %
digits( p ) := dPos;
powers( p, dPos ) := carry;
if lowest( carry ) < 0 then lowest( carry ) := p;
end if_carry_eq_0__ ;
% find the two digit numbers %
for n := 10 until 21 do begin
if lowest( n ) < 0 then begin
integer h, l;
h := n div 10;
l := n rem 10;
for d := digits( p ) - 1 step -1 until 1 do begin
if powers( p, d ) = l and powers( p, d + 1 ) = h then lowest( n ) := p
end for_d
end if_lowest_n_lt_0
end for_n
end for_p ;
% show the lowest powers that contain the numbers 0..21 %
for n := 0 until 21 do begin
integer p;
p := lowest( n );
write( i_w := 2, s_w := 0, n, " in 6^", p, ": " );
for d := digits( p ) step -1 until 1 do writeon( i_w := 1, s_w := 0, powers( p, d ) )
end for_n
end.</lang>
{{out}}
<pre>
0 in 6^ 9: 10077696
1 in 6^ 0: 1
2 in 6^ 3: 216
3 in 6^ 2: 36
4 in 6^ 6: 46656
5 in 6^ 6: 46656
6 in 6^ 1: 6
7 in 6^ 5: 7776
8 in 6^12: 2176782336
9 in 6^ 4: 1296
10 in 6^ 9: 10077696
11 in 6^16: 2821109907456
12 in 6^ 4: 1296
13 in 6^13: 13060694016
14 in 6^28: 6140942214464815497216
15 in 6^18: 101559956668416
16 in 6^ 3: 216
17 in 6^10: 60466176
18 in 6^15: 470184984576
19 in 6^21: 21936950640377856
20 in 6^26: 170581728179578208256
21 in 6^ 3: 216
</pre>
=={{header|AWK}}==
<lang AWK>
| |||