Permuted multiples: Difference between revisions
(Added C++ solution) |
(Added XPL0 example.) |
||
| Line 829: | Line 829: | ||
5 x n = 714285 |
5 x n = 714285 |
||
6 x n = 857142 |
6 x n = 857142 |
||
</pre> |
|||
=={{header|XPL0}}== |
|||
<lang XPL0>func Digits(N); \Return counts of digits packed in 30 bits |
|||
int N, Sums; |
|||
[Sums:= 0; |
|||
repeat N:= N/10; |
|||
Sums:= Sums + 1<<(rem(0)*3); |
|||
until N = 0; |
|||
return Sums; |
|||
]; |
|||
int N, Sums; |
|||
[N:= 1; |
|||
loop [Sums:= Digits(N*2); |
|||
if Digits(N*3) = Sums then |
|||
if Digits(N*4) = Sums then |
|||
if Digits(N*5) = Sums then |
|||
if Digits(N*6) = Sums then |
|||
quit; |
|||
N:= N+1; |
|||
]; |
|||
IntOut(0, N); |
|||
]</lang> |
|||
{{out}} |
|||
<pre> |
|||
142857 |
|||
</pre> |
</pre> |
||
Revision as of 17:12, 24 August 2021
- Attribution
The following task is taken from Project Euler.
- Task
Find the smallest positive integer n such that, when expressed in decimal, 2*n, 3*n, 4*n, 5*n, and 6*n contain exactly the same digits but in a different order.
AppleScript
— except that the 'steps' figure here is cumulative. Also, for six different numbers to have the same digits, each must have at least three digits, none of which can be 0. So the lowest possible value of n in this respect is 123. But for a number beginning with 1 to stand any chance of containing the same digits as both a number that's 2 times it and another that's 6 times it, it must also contain at least one digit that's no less than 2 and another that's no less than 6. The lowest combination of these is 26, which also produces a multiple of 3 when added to a power of 10. So this makes a slightly better post-power start point than 2, saving eight steps per power. ;)
Shifting the 26 up against the 1 obviously keeps the "at least" condition satisfied for longer during the subsequent additions of 3 at the low end and gives a start point much closer to the next power. This more than halves the number of steps performed and thus the time taken. It also produces the correct result(s), but I can't see that it's logically bound to do so. :\
<lang applescript>use AppleScript version "2.3.1" -- Mac OS X 10.9 (Mavericks) or later. use sorter : script "Insertion Sort" -- <https://www.rosettacode.org/wiki/Sorting_algorithms/Insertion_sort#AppleScript>
on decDigits(n)
set digits to {n mod 10 as integer}
set n to n div 10
repeat until (n = 0)
set beginning of digits to n mod 10 as integer
set n to n div 10
end repeat
return digits
end decDigits
on join(lst, delim)
set astid to AppleScript's text item delimiters set AppleScript's text item delimiters to delim set txt to lst as text set AppleScript's text item delimiters to astid return txt
end join
on task()
set {output, n, n10, steps} to {{}, 126, 1000, 0}
repeat
if (n * 6 < n10) then
set steps to steps + 1
set nl to decDigits(n)
tell sorter to sort(nl, 1, -1)
set found to true
repeat with i from 2 to 6
set inl to decDigits(n * i)
tell sorter to sort(inl, 1, -1)
if (inl ≠ nl) then
set found to false
exit repeat
end if
end repeat
if (found) then exit repeat
set n to n + 3
else
set end of output to "Nothing below " & n10 & (" (" & steps & " steps)")
set n to n10 + 26 -- set n to n10 * 1.26 as integer
set n10 to n10 * 10
-- set steps to 0
end if
end repeat
set end of output to " n = " & n & (" (" & steps & " steps altogether)")
repeat with i from 2 to 6
set end of output to (i as text) & " * n = " & i * n
end repeat
return join(output, linefeed)
end task
task()</lang>
- Output:
Using 'set n to n10 + 26': <lang applescript>"Nothing below 1000 (14 steps) Nothing below 10000 (228 steps) Nothing below 100000 (2442 steps)
n = 142857 (16720 steps altogether)
2 * n = 285714 3 * n = 428571 4 * n = 571428 5 * n = 714285 6 * n = 857142"</lang>
- Output:
Using 'set n to n10 * 1.26 as integer': <lang applescript>"Nothing below 1000 (14 steps) Nothing below 10000 (150 steps) Nothing below 100000 (1506 steps)
n = 142857 (7126 steps altogether)
2 * n = 285714 3 * n = 428571 4 * n = 571428 5 * n = 714285 6 * n = 857142" </lang>
C++
<lang cpp>#include <array>
- include <iostream>
using digits = std::array<unsigned int, 10>;
digits get_digits(unsigned int n) {
digits d = {};
do {
++d[n % 10];
n /= 10;
} while (n > 0);
return d;
}
// Returns true if n, 2n, ..., 6n all have the same base 10 digits. bool same_digits(unsigned int n) {
digits d = get_digits(n);
for (unsigned int i = 0, m = n; i < 5; ++i) {
m += n;
if (get_digits(m) != d)
return false;
}
return true;
}
int main() {
for (unsigned int p = 100; ; p *= 10) {
unsigned int max = (p * 10) / 6;
for (unsigned int n = p + 2; n <= max; n += 3) {
if (same_digits(n)) {
std::cout << " n = " << n << '\n';
for (unsigned int i = 2; i <= 6; ++i)
std::cout << i << "n = " << n * i << '\n';
return 0;
}
}
}
}</lang>
- Output:
n = 142857 2n = 285714 3n = 428571 4n = 571428 5n = 714285 6n = 857142
F#
<lang fsharp> // Permuted multiples. Nigel Galloway: August 18th., 2021 let fG n g=let rec fN g=[if g>0 then yield g%10; yield! fN(g/10)] in List.sort(fN n)=List.sort(fN g) let n=Seq.initInfinite((+)2)|>Seq.collect(fun n->seq{(pown 10 n)+2..3..(pown 10 (n+1))/6})|>Seq.find(fun g->let fN=fG g in fN(g*2)&&fN(g*3)&&fN(g*4)&&fN(g*5)&&fN(g*6)) printfn $"The solution to Project Euler 52 is %d{n}" </lang>
- Output:
The solution to Project Euler 52 is 142857
Factor
<lang factor>USING: formatting io kernel lists lists.lazy math math.ranges math.vectors numspec present prettyprint sequences sets ;
- multiples ( n -- seq )
[ 2 * ] [ 6 * ] [ ] tri <range> [ present ] map ;
- all-set-eq? ( seq -- ? )
dup ?first [ set= ] curry all? ;
! Ordered lazy list of numbers that start with a '1' digit NUMSPEC: starting-with-one 1 1_ ... ;
- smallest-permuted-multiple ( -- n )
starting-with-one [ multiples all-set-eq? ] lfilter car ;
{ 2 3 4 5 6 } " n: " write smallest-permuted-multiple dup . over n*v [ "×%d: %d\n" printf ] 2each</lang>
- Output:
n: 142857 ×2: 285714 ×3: 428571 ×4: 571428 ×5: 714285 ×6: 857142
Go
<lang go>package main
import (
"fmt" "rcu" "sort"
)
// assumes l1 is sorted but l2 is not func areSame(l1, l2 []int) bool {
if len(l1) != len(l2) {
return false
}
sort.Ints(l2)
for i := 0; i < len(l1); i++ {
if l1[i] != l2[i] {
return false
}
}
return true
}
func main() {
i := 100 // clearly a 1 or 2 digit number is impossible
nextPow := 1000
for {
digits := rcu.Digits(i, 10)
if digits[0] != 1 {
i = nextPow
nextPow *= 10
continue
}
sort.Ints(digits)
allSame := true
for j := 2; j <= 6; j++ {
digits2 := rcu.Digits(i*j, 10)
if !areSame(digits, digits2) {
allSame = false
break
}
}
if allSame {
fmt.Println("The smallest positive integer n for which the following")
fmt.Println("multiples contain exactly the same digits is:")
fmt.Println(" n =", i)
for k := 2; k <= 6; k++ {
fmt.Printf("%d x n = %d\n", k, k*i)
}
return
}
i = i + 1
}
}</lang>
- Output:
The smallest positive integer n for which the following
multiples contain exactly the same digits is:
n = 142857
2 x n = 285714
3 x n = 428571
4 x n = 571428
5 x n = 714285
6 x n = 857142
Julia
<lang julia>n = minimum([n for n in 1:2000000 if sort(digits(2n)) == sort(digits(3n)) == sort(digits(4n)) == sort(digits(5n))== sort(digits(6n))]) println("n: $n, 2n: $(2n), 3n: $(3n), 4n: $(4n), 5n: $(5n), 6n: $(6n)")
</lang>
- Output:
n: 142857, 2n: 285714, 3n: 428571, 4n: 571428, 5n: 714285, 6n: 857142
Nim
Searching among multiples of 3 between 102 and 1_000 div 6, 1_002 and 10_000 div 6, 10_002 and 100_000 div 6, etc. (see discussion).
<lang Nim>from algorithm import sorted
func search(): int =
var start = 100
while true:
for i in countup(start + 2, 10 * start div 6, 3):
let digits = sorted($i)
block check:
for j in 2..6:
if sorted($(i * j)) != digits:
break check
# Found.
return i
start *= 10
let n = search() echo " n = ", n for k in 2..6:
echo k, "n = ", k * n</lang>
- Output:
n = 142857 2n = 285714 3n = 428571 4n = 571428 5n = 714285 6n = 857142
Pascal
Create an array of the digits fixed 1 as first digit and 0 "1023456789"
Adding done digit by digit, so no conversion needed.
Using set of tdigit ,so no sort of digits is required.
Don't use the fact, that second digit must be < 6.Runtime negligible.
<lang pascal>program euler52;
{$IFDEF FPC}
{$MOde DElphi} {$Optimization On,ALL}
{$else}
{$Apptype console}
{$ENDIF} uses
sysutils;
const
BaseConvDgt :array[0..35] of char = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'; MAXBASE = 12;//
type
TUsedDigits = array[0..MAXBASE-1] of byte; tDigitsInUse = set of 0..MAXBASE-1;
var {$ALIGN 16}
UsedDigits :tUsedDigits;
{$ALIGN 16}
gblMaxDepth, steps, base,maxmul : NativeInt; found : boolean; function AddOne(var SumDigits:tUsedDigits;const UsedDigits: tUsedDigits):NativeInt;forward;
function ConvBaseToStr(const UsedDigits :tUsedDigits):string; var
i,j:NativeUint;
Begin
setlength(result,gblMaxdepth+1); j := 1; For i := 0 to gblMaxdepth do begin result[j] := BaseConvDgt[UsedDigits[i]]; inc(j); end;
end;
procedure Out_MaxMul(const UsedDigits :tUsedDigits); var
j : NativeInt; SumDigits :tUsedDigits;
begin
writeln('With ',gblMaxdepth+1,' digits');
sumDigits := UsedDigits;
write(' 1x :',ConvBaseToStr(UsedDigits));
For j := 2 to MaxMul do
Begin
AddOne(SumDigits,UsedDigits);
write(j:2,'x:',ConvBaseToStr(SumDigits));
end;
writeln;
writeln('steps ',steps);
end;
procedure InitUsed; Var
i : NativeInt;
Begin
For i := 2 to BASE-1 do UsedDigits[i] := i; UsedDigits[0] := 1; UsedDigits[1] := 0;
end;
function GetUsedSet(const UsedDigits: tUsedDigits):tDigitsInUse; var
i : NativeInt;
begin
result := []; For i := 0 to gblMaxDepth do include(result,UsedDigits[i]);
end;
function AddOne(var SumDigits:tUsedDigits;const UsedDigits: tUsedDigits):NativeInt; //add and return carry var
s,i: NativeUint;
begin
result := 0; For i := gblMaxdepth downto 0 do Begin s := UsedDigits[i]+SumDigits[i]+result; result := ord(s >= BASE);// 0 or 1
// if result >0 then s -= base;//runtime Base=12 Done in 2.097 -> Done in 1.647
s -= result*base; SumDigits[i] := s; end;
end;
function CheckMultiples(const UsedDigits: tUsedDigits;OrgInUse:tDigitsInUse):NativeInt; var {$ALIGN 16}
SumDigits :tUsedDigits; j : integer;
begin
result := 0;
SumDigits := UsedDigits;
j := 2;// first doubled
repeat
if AddOne(SumDigits,UsedDigits) >0 then
break;
if GetUsedSet(SumDigits) <> OrgInUse then
break;
inc(j);
until j > MaxMul;
found := j > MaxMul;
if found then
Out_MaxMul(UsedDigits);
end;
procedure GetNextUsedDigit(StartIdx:NativeInt); var
i : NativeInt; DigitTaken: Byte;
Begin
For i := StartIDx to BASE-1 do Begin //Stop after first found if found then BREAK; DigitTaken := UsedDigits[i]; //swap i with Startidx UsedDigits[i]:= UsedDigits[StartIdx]; UsedDigits[StartIdx] := DigitTaken;
inc(steps);
IF StartIdx <gblMaxDepth then
GetNextUsedDigit(StartIdx+1)
else
CheckMultiples(UsedDigits,GetUsedSet(UsedDigits));
//undo swap i with Startidx
UsedDigits[StartIdx] := UsedDigits[i];
UsedDigits[i]:= DigitTaken;
end;
end;
var
T : INt64;
Begin
T := GetTickCount64;
// For base := 4 to MAXBASE do
For base := 4 to 10 do
Begin
Writeln('Base ',base);
MaxMul := Base-2;
If base = 10 then
MaxMul := 6;
InitUsed;
steps := 0;
For gblMaxDepth := 1 to BASE-1 do
Begin
found := false;
GetNextUsedDigit(1);
end;
writeln;
end;
T := GetTickCount64-T;
write('Done in ',T/1000:0:3,' s');
{$IFDEF WINdows}
readln;
{$ENDIF}
end.</lang>
- Output:
TIO.RUN Base 4 With 3 digits 1x :102 2x:210 steps 5 With 4 digits 1x :1032 2x:2130 steps 10 Base 5 Base 6 With 5 digits 1x :10432 2x:21304 3x:32140 4x:43012 steps 139 With 6 digits 1x :105432 2x:215304 3x:325140 4x:435012 steps 197 Base 7 Base 8 With 7 digits 1x :1065432 2x:2153064 3x:3240516 4x:4326150 5x:5413602 6x:6501234 steps 5945 With 8 digits 1x :10765432 2x:21753064 3x:32740516 4x:43726150 5x:54713602 6x:65701234 steps 7793 Base 9 Base 10 With 6 digits 1x :142857 2x:285714 3x:428571 4x:571428 5x:714285 6x:857142 steps 10725 With 7 digits 1x :1428570 2x:2857140 3x:4285710 4x:5714280 5x:7142850 6x:8571420 steps 37956 With 8 digits 1x :14298570 2x:28597140 3x:42895710 4x:57194280 5x:71492850 6x:85791420 steps 128297 Done in 0.044 s
Perl
<lang perl>#!/usr/bin/perl
use strict; # https://rosettacode.org/wiki/Permuted_multiples use warnings;
my $n = 3; 1 while do {
length($n += 3) < length 6 * $n and $n = 1 . $n =~ s/./0/gr + 2; my $sorted = join , sort split //, $n * 6; $sorted ne join , sort split //, $n * 1 or $sorted ne join , sort split //, $n * 2 or $sorted ne join , sort split //, $n * 3 or $sorted ne join , sort split //, $n * 4 or $sorted ne join , sort split //, $n * 5 };
printf " n %s\n", $n; printf "%dn %s\n", $_ , $n * $_ for 2 .. 6;</lang>
- Output:
n 142857 2n 285714 3n 428571 4n 571428 5n 714285 6n 857142
Phix
Maintain a limit (n10) and bump the iteration whenever *6 increases the number of digits, which (as [was] shown) cuts the number of iterations by a factor of nearly thirteen and a half times (as in eg [as was] 67 iterations instead of 900 to find nothing in 100..1,000). Also as noted on the talk page, since sum(digits(3n)) is a multiple of 3 and it uses the same digits as n, then sum(digits(n)) will also be the very same multiple of 3 and hence n must (also) be divisible by 3, so we can start each longer-digits iteration on 10^k+2 (since remainder(10^k,3) is always 1) and employ a step of 3, and enjoy a better than 40-fold overall reduction in iterations.
with javascript_semantics atom t0 = time() integer n = 3, n10 = 10, steps = 0 constant fmt=""" %s positive integer n for which (2..6)*n contain the same digits: n = %,d (%,d steps, hmmm...) 2 x n = %,d 3 x n = %,d 4 x n = %,d 5 x n = %,d 6 x n = %,d """, limit = iff(platform()=JS?1e7:1e9) string nowtelse = "Nothing", smother = "Smallest" while true do if n*6>=n10 then printf(1,"%s less than %,d (%,d steps)\n",{nowtelse,n10,steps}) if n10>=limit then exit end if n = n10+2 n10 *= 10 steps = 0 else string ns = sort(sprintf("%d",n)) integer i -- (to test after loop) for i=2 to 6 do string ins = sort(sprintf("%d",n*i)) if ins!=ns then exit end if end for if i=7 then printf(1,fmt,{smother,n,steps} & sq_mul(n,tagset(6,2))) nowtelse = "Nothing else" smother = "Another" exit -- (see below) end if n += 3 steps += 1 end if end while ?elapsed(time()-t0)
- Output:
Nothing less than 10 (0 steps)
Nothing less than 100 (2 steps)
Nothing less than 1,000 (22 steps)
Nothing less than 10,000 (222 steps)
Nothing less than 100,000 (2,222 steps)
Smallest positive integer n for which (2..6)*n contain the same digits:
n = 142,857 (14,285 steps, hmmm...)
2 x n = 285,714
3 x n = 428,571
4 x n = 571,428
5 x n = 714,285
6 x n = 857,142
"0.1s"
extended output
If we comment out that "exit -- (see below)", as per the AppleScript comments and the Pascal output, some patterns start to emerge in the values and number of steps: *10 is a bit of a given, whereas "insert 9s before the 8" is (for me) a bit more unexpected. Be warned: on the desktop, 1e8 takes about 9s, 1e9 about 90s, so I'll predict 1e10 would take 15mins (and need 64bit) and I'll not try to compete with Pascal in terms of performance, though I am getting very different results above 1e7. Under pwa/p2js 1e8 takes about 30s (meh) so I've limited it to 1e7 (2.3s).
Nothing else less than 1,000,000 (22,222 steps)
Another positive integer n for which (2..6)*n contain the same digits:
n = 1,428,570 (142,856 steps, hmmm...)
2 x n = 2,857,140
3 x n = 4,285,710
4 x n = 5,714,280
5 x n = 7,142,850
6 x n = 8,571,420
Another positive integer n for which (2..6)*n contain the same digits:
n = 1,429,857 (143,285 steps, hmmm...)
2 x n = 2,859,714
3 x n = 4,289,571
4 x n = 5,719,428
5 x n = 7,149,285
6 x n = 8,579,142
Nothing else less than 10,000,000 (222,222 steps)
Another positive integer n for which (2..6)*n contain the same digits:
n = 14,285,700 (1,428,566 steps, hmmm...)
2 x n = 28,571,400
3 x n = 42,857,100
4 x n = 57,142,800
5 x n = 71,428,500
6 x n = 85,714,200
Another positive integer n for which (2..6)*n contain the same digits:
n = 14,298,570 (1,432,856 steps, hmmm...)
2 x n = 28,597,140
3 x n = 42,895,710
4 x n = 57,194,280
5 x n = 71,492,850
6 x n = 85,791,420
Another positive integer n for which (2..6)*n contain the same digits:
n = 14,299,857 (1,433,285 steps, hmmm...)
2 x n = 28,599,714
3 x n = 42,899,571
4 x n = 57,199,428
5 x n = 71,499,285
6 x n = 85,799,142
Nothing else less than 100,000,000 (2,222,222 steps)
Another positive integer n for which (2..6)*n contain the same digits:
n = 142,857,000 (14,285,666 steps, hmmm...)
2 x n = 285,714,000
3 x n = 428,571,000
4 x n = 571,428,000
5 x n = 714,285,000
6 x n = 857,142,000
Another positive integer n for which (2..6)*n contain the same digits:
n = 142,985,700 (14,328,566 steps, hmmm...)
2 x n = 285,971,400
3 x n = 428,957,100
4 x n = 571,942,800
5 x n = 714,928,500
6 x n = 857,914,200
Another positive integer n for which (2..6)*n contain the same digits:
n = 142,998,570 (14,332,856 steps, hmmm...)
2 x n = 285,997,140
3 x n = 428,995,710
4 x n = 571,994,280
5 x n = 714,992,850
6 x n = 857,991,420
Another positive integer n for which (2..6)*n contain the same digits:
n = 142,999,857 (14,333,285 steps, hmmm...)
2 x n = 285,999,714
3 x n = 428,999,571
4 x n = 571,999,428
5 x n = 714,999,285
6 x n = 857,999,142
Nothing else less than 1,000,000,000 (22,222,222 steps)
I believe that last pattern will be continue to be valid no matter how many 9s are inserted in the middle, and I doubt that any further patterns would emerge.
Raku
<lang perl6>put display (^∞).map(1 ~ *).race.map( -> \n { next unless [eq] (2,3,4,5,6).map: { (n × $_).comb.sort.join }; n } ).first;
sub display ($n) { join "\n", " n: $n", (2..6).map: { "×$_: {$n×$_}" } }</lang>
- Output:
n: 142857 ×2: 285714 ×3: 428571 ×4: 571428 ×5: 714285 ×6: 857142
REXX
<lang rexx>/*REXX program finds and displays the smallest positive integer n such that ··· */ /*───────────────────────── 2*n, 3*n, 4*5, 5*6, and 6*n contain the same decimal digits.*/
do n=1 /*increment N from unity 'til answer.*/
b= 2*n /*calculate the product of: 2*n */
t= 3*n /* " " " " 3*n */
if verify(t, b)>0 then iterate /*T doesn't have required digits? Skip*/
q= 4*n /*calculate the product of: 4*n */
if verify(q, b)>0 then iterate /*Q doesn't have required digits? Skip*/
if verify(q, t)>0 then iterate /*" " " " " " */
v= 5*n /*calculate the product of: 5*n */
if verify(v, b)<0 then iterate /*V doesn't have required digits? Skip*/
if verify(v, t)>0 then iterate /*" " " " " " */
if verify(v, q)>0 then iterate /*" " " " " " */
s= 6*n /*calculate the product of: 6*n */
if verify(s, b)>0 then iterate /*S doesn't have required digits? Skip*/
if verify(s, t)>0 then iterate /*" " " " " " */
if verify(s, q)>0 then iterate /*" " " " " " */
if verify(s, v)>0 then iterate /*" " " " " " */
say ' n =' commas(n) /*display the value of: n */
say ' 2*n =' commas(b) /* " " " " 2*n */
say ' 3*n =' commas(t) /* " " " " 3*n */
say ' 4*n =' commas(q) /* " " " " 4*n */
say ' 5*n =' commas(v) /* " " " " 5*n */
say ' 6*n =' commas(s) /* " " " " 6*n */
leave /*found the N number, time to leave.*/
end /*n*/
exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ?</lang>
- output when using the internal default input:
n = 142,857
2*n = 285,714
3*n = 428,571
4*n = 571,428
5*n = 714,285
6*n = 857,142
Ring
<lang ring> load "stdlib.ring"
see "working..." + nl see "Permuted multiples are:" + nl per = list(6) perm = list(6)
for n = 1 to 1000000
for x = 2 to 6
perm[x] = []
next
perStr = list(6)
for z = 2 to 6
per[z] = n*z
perStr[z] = string(per[z])
for m = 1 to len(perStr[z])
add(perm[z],perStr[z][m])
next
next
for y = 2 to 6
perm[y] = sort(perm[y])
perStr[y] = list2str(perm[y])
perStr[y] = substr(perStr[y],nl,"")
next
if perStr[2] = perStr[3] and perStr[2] = perStr[4] and perStr[2] = perStr[5] and perStr[2] = perStr[6]
see "n = " + n + nl
see "2*n = " + (n*2) + nl
see "3*n = " + (n*3) + nl
see "4*n = " + (n*4) + nl
see "5*n = " + (n*5) + nl
see "6*n = " + (n*6) + nl
exit
ok
next
see "done..." + nl </lang>
- Output:
working... Permuted multiples are: n = 142857 2*n = 285714 3*n = 428571 4*n = 571428 5*n = 714285 6*n = 857142 done...
Wren
One thing that's immediately clear is that the number must begin with '1' otherwise the higher multiples will have more digits than it has. <lang ecmascript>import "/math" for Int
// assumes l1 is sorted but l2 is not var areSame = Fn.new { |l1, l2|
if (l1.count != l2.count) return false
l2.sort()
for (i in 0...l1.count) {
if (l1[i] != l2[i]) return false
}
return true
}
var i = 100 // clearly a 1 or 2 digit number is impossible var nextPow = 1000 while (true) {
var digits = Int.digits(i)
if (digits[0] != 1) {
i = nextPow
nextPow = nextPow * 10
continue
}
digits.sort()
var allSame = true
for (j in 2..6) {
var digits2 = Int.digits(i * j)
if (!areSame.call(digits, digits2)) {
allSame = false
break
}
}
if (allSame) {
System.print("The smallest positive integer n for which the following")
System.print("multiples contain exactly the same digits is:")
System.print(" n = %(i)")
for (k in 2..6) System.print("%(k) x n = %(k * i)")
return
}
i = i + 1
}</lang>
- Output:
The smallest positive integer n for which the following
multiples contain exactly the same digits is:
n = 142857
2 x n = 285714
3 x n = 428571
4 x n = 571428
5 x n = 714285
6 x n = 857142
XPL0
<lang XPL0>func Digits(N); \Return counts of digits packed in 30 bits int N, Sums; [Sums:= 0; repeat N:= N/10;
Sums:= Sums + 1<<(rem(0)*3);
until N = 0; return Sums; ];
int N, Sums; [N:= 1; loop [Sums:= Digits(N*2);
if Digits(N*3) = Sums then
if Digits(N*4) = Sums then
if Digits(N*5) = Sums then
if Digits(N*6) = Sums then
quit;
N:= N+1;
];
IntOut(0, N); ]</lang>
- Output:
142857