Rosetta Code

Permuted multiples: Difference between revisions

Page Discussion

Permuted multiples (view source)

Revision as of 12:51, 24 January 2024

8,370 bytes added ,  3 months ago
m
→‎{{header|Wren}}: Minor tidy
(add FreeBASIC)
m (→‎{{header|Wren}}: Minor tidy)
 
(13 intermediate revisions by 6 users not shown)
Line 7:
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.
<br><br>
 
=={{header|APL}}==
<syntaxhighlight lang="apl">{(⍳6)×{⍵+1}⍣{1=≢∪{⍵[⍋⍵]}¨⍕¨⍺×⍳6}⊢⍵} 123</syntaxhighlight>
{{out}}
<pre>142857 285714 428571 571428 714285 857142</pre>
 
=={{header|AppleScript}}==
Line 13 ⟶ 18:
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. :\
 
<langsyntaxhighlight 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>
 
Line 68 ⟶ 73:
end task
 
task()</langsyntaxhighlight>
 
{{output}}
Using 'set n to n10 + 26':
<langsyntaxhighlight lang="applescript">"Nothing below 1000 (14 steps)
Nothing below 10000 (228 steps)
Nothing below 100000 (2442 steps)
Line 80 ⟶ 85:
4 * n = 571428
5 * n = 714285
6 * n = 857142"</langsyntaxhighlight>
{{output}}
Using 'set n to n10 * 1.26 as integer':
<langsyntaxhighlight lang="applescript">"Nothing below 1000 (14 steps)
Nothing below 10000 (150 steps)
Nothing below 100000 (1506 steps)
Line 92 ⟶ 97:
5 * n = 714285
6 * n = 857142"
</syntaxhighlight>
</lang>
 
=={{header|Arturo}}==
 
<syntaxhighlight lang="arturo">permutable?: function [n]->
one? unique map 2..6 'x -> sort digits x*n
 
firstPermutable: first select.first 1..∞ => permutable?
 
print [firstPermutable join.with:" " to [:string] map 2..6 'x -> x*firstPermutable]</syntaxhighlight>
 
{{out}}
 
<pre>142857 285714 428571 571428 714285 857142</pre>
 
=={{header|C}}==
<syntaxhighlight lang="c">#include <stdio.h>
#include <stdbool.h>
 
/* Find the set of digits of N, expressed as a number
where the N'th digit represents the amount of times
that digit occurs. */
int digit_set(int n) {
static const int powers[] = {
1, 10, 100, 1000, 10000, 100000, 1000000, 10000000,
100000000, 1000000000
};
int dset;
for (dset = 0; n; n /= 10)
dset += powers[n % 10];
return dset;
}
 
/* See if for a given N, [1..6]*N all have the same digits */
bool is_permuted_multiple(int n) {
int dset = digit_set(n);
for (int mult = 2; mult <= 6; mult++)
if (dset != digit_set(n * mult)) return false;
return true;
}
 
/* Find the first matching number */
int main() {
int n;
for (n = 123; !is_permuted_multiple(n); n++);
for (int mult = 1; mult <= 6; mult++)
printf("%d * n = %d\n", mult, n*mult);
return 0;
}</syntaxhighlight>
{{out}}
<pre>1 * n = 142857
2 * n = 285714
3 * n = 428571
4 * n = 571428
5 * n = 714285
6 * n = 857142</pre>
 
=={{header|C++}}==
<langsyntaxhighlight lang="cpp">#include <array>
#include <iostream>
 
Line 132 ⟶ 193:
}
}
}</langsyntaxhighlight>
 
{{out}}
Line 143 ⟶ 204:
6n = 857142
</pre>
 
=={{header|CLU}}==
<syntaxhighlight lang="clu">% Get all digits of a number
digits = iter (n: int) yields (int)
while n>0 do
yield(n//10)
n := n/10
end
end digits
 
% Return the amount of times each digit occurs
digit_set = proc (n: int) returns (sequence[int])
ds: array[int] := array[int]$fill(0,10,0)
for d: int in digits(n) do
ds[d] := ds[d] + 1
end
return(sequence[int]$a2s(ds))
end digit_set
 
% See if for an integer N, [1..6]*N all have the same digits
permuted_multiple = proc (n: int) returns (bool)
ds: sequence[int] := digit_set(n)
for mult: int in int$from_to(2,6) do
if digit_set(mult*n) ~= ds then return(false) end
end
return(true)
end permuted_multiple
 
% Find the first number for which this holds
start_up = proc ()
n: int := 123
while ~permuted_multiple(n) do n := n+1 end
po: stream := stream$primary_output()
for mult: int in int$from_to(1,6) do
stream$putl(po, int$unparse(mult) || " * n = " || int$unparse(mult*n))
end
end start_up</syntaxhighlight>
{{out}}
<pre>1 * n = 142857
2 * n = 285714
3 * n = 428571
4 * n = 571428
5 * n = 714285
6 * n = 857142</pre>
 
=={{header|Cowgol}}==
<syntaxhighlight lang="cowgol">include "cowgol.coh";
 
# Return the amount of times each digit appears in a number
# (as long as none appears more than 9 times that is)
sub digit_set(n: uint32): (set: uint32) is
var ten_powers: uint32[] := {
1, 10, 100, 1000, 10000, 100000, 1000000,
10000000, 100000000, 1000000000
};
set := 0;
while n>0 loop
var digit := (n % 10) as uint8;
n := n / 10;
set := set + ten_powers[digit];
end loop;
end sub;
 
# See if for an integer N, [1..6]*N all have the same digits
sub permuted_multiple(n: uint32): (ok: uint8) is
ok := 0;
var ds := digit_set(n);
var i: uint32 := 2;
while i<=6 loop
if ds != digit_set(i * n) then return; end if;
i := i + 1;
end loop;
ok := 1;
end sub;
 
# Find the first matching number
var n: uint32 := 123;
while permuted_multiple(n) == 0 loop
n := n + 1;
end loop;
 
# Print the number and its multiples
var i: uint32 := 1;
while i<=6 loop
print_i32(i);
print(" * n = ");
print_i32(n * i);
print_nl();
i := i+1;
end loop;</syntaxhighlight>
{{out}}
<pre>1 * n = 142857
2 * n = 285714
3 * n = 428571
4 * n = 571428
5 * n = 714285
6 * n = 857142</pre>
 
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
 
 
<syntaxhighlight lang="Delphi">
 
 
function IsPMultiple(N: integer): boolean;
{Test if N*2, N*3, N*4, N*5, N*6 have the same digits}
var NT: integer;
var SA: array [0..4] of string;
var I,J: integer;
var SL: TStringList;
var IA: TIntegerDynArray;
begin
SL:=TStringList.Create;
try
Result:=False;
for I:=0 to 4 do
begin
{Do N*2, N*3, N*4, N*5, N*6}
NT:=N * (I+2);
{Get digits}
GetDigits(NT,IA);
{Store each digit in String List}
SL.Clear;
for J:=0 to High(IA) do SL.Add(IntToStr(IA[J]));
{Sort list}
SL.Sort;
{Put sorted digits in a string}
SA[I]:='';
for J:=0 to SL.Count-1 do SA[I]:=SA[I]+SL[J][1];
end;
{Compare all strings}
for I:=0 to High(SA)-1 do
if SA[I]<>SA[I+1] then exit;
Result:=True;
finally SL.Free; end;
end;
 
procedure ShowPermutedMultiples(Memo: TMemo);
var I,J: integer;
begin
for I:=1 to high(integer) do
if IsPMultiple(I) then
begin
for J:=1 to 6 do
Memo.Lines.Add(Format('N * %D = %D',[J,I*J]));
break;
end;
end;
 
 
</syntaxhighlight>
{{out}}
<pre>
N * 1 = 142,857
N * 2 = 285,714
N * 3 = 428,571
N * 4 = 571,428
N * 5 = 714,285
N * 6 = 857,142
 
Elapsed Time: 4.030 Sec.
 
</pre>
 
 
=={{header|F_Sharp|F#}}==
<langsyntaxhighlight 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}"
</syntaxhighlight>
</lang>
{{out}}
<pre>
The solution to Project Euler 52 is 142857
</pre>
 
=={{header|Factor}}==
{{libheader|Factor-numspec}}
{{works with|Factor|0.99 2021-06-02}}
<langsyntaxhighlight lang="factor">USING: formatting io kernel lists lists.lazy math math.ranges
math.vectors numspec present prettyprint sequences sets ;
 
Line 174 ⟶ 403:
 
{ 2 3 4 5 6 } " n: " write smallest-permuted-multiple dup .
over n*v [ "×%d: %d\n" printf ] 2each</langsyntaxhighlight>
{{out}}
<pre>
Line 186 ⟶ 415:
 
=={{header|FreeBASIC}}==
<langsyntaxhighlight lang="freebasic">function sort(s as string) as string
'quick and dirty bubblesort, not the focus of this exercise
dim as string t = s
Line 216 ⟶ 445:
print n, 2*n, 3*n, 4*n, 5*n, 6*n
end
loop</langsyntaxhighlight>
{{out}}<pre>
142857 285714 428571 571428 714285 857142
Line 224 ⟶ 453:
{{trans|Wren}}
{{libheader|Go-rcu}}
<langsyntaxhighlight lang="go">package main
 
import (
Line 276 ⟶ 505:
i = i + 1
}
}</langsyntaxhighlight>
 
{{out}}
Line 289 ⟶ 518:
6 x n = 857142
</pre>
 
=={{header|J}}==
Because 1*n and 6*n have the same number of digits, and because 2*6 is 12, we know that the first digit of n must be 1. And, because 1*m is different for any m in 1 2 3 4 5 and 6, we know that n must contain at least 6 different digits. So n must be at least 123456. And, as mentioned on the talk page, n must be divisible by 3. (And, of course, 123456 is divisible by 3.)
 
In other words:
<syntaxhighlight lang=J> D*/(3+])^:(D {{1<#~./:"1~10#.inv y*m}})^:_(10#.D=:1+i.6)
142857 285714 428571 571428 714285 857142</syntaxhighlight>
 
Here, we start with <code>123456</code>, and then add <code>3</code> to it until the digits appearing in its multiples by <code>D</code>, when sorted, are all the same. (<code>D</code> is <code>1 2 3 4 5 6</code>.)
 
It's worth noting here that
<syntaxhighlight lang=J> <.1e6%7
142857</syntaxhighlight>
 
=={{header|Java}}==
<langsyntaxhighlight lang="java">import java.util.*;
 
public class PermutedMultiples {
Line 327 ⟶ 569:
return digits;
}
}</langsyntaxhighlight>
 
{{out}}
Line 344 ⟶ 586:
 
The following uses a simple generate-and-test approach but with early backtracking, so it's quite reasonable.
<langsyntaxhighlight lang="jq">def digits: tostring | explode;
 
first(range(1; infinite)
| . as $i
| (digits|sort) as $reference
| select(all(range(2;7); $reference == ((. * $i) | digits | sort))) )</langsyntaxhighlight>
{{out}}
<pre>
Line 357 ⟶ 599:
 
=={{header|Julia}}==
<langsyntaxhighlight 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)")
</langsyntaxhighlight>{{out}}
<pre>
n: 142857, 2n: 285714, 3n: 428571, 4n: 571428, 5n: 714285, 6n: 857142
</pre>
 
=={{header|MAD}}==
<syntaxhighlight lang="mad"> NORMAL MODE IS INTEGER
VECTOR VALUES TENMUL = 1,10,100,1000,10000,100000,
1 1000000,10000000,100000000,1000000000
VECTOR VALUES FMT = $I1,8H * N = ,I6*$
INTERNAL FUNCTION(XX)
ENTRY TO DIGSET.
X = XX
DSET = 0
DIGIT WHENEVER X.E.0, FUNCTION RETURN DSET
NXT = X/10
DSET = DSET + TENMUL(X-NXT*10)
X = NXT
TRANSFER TO DIGIT
END OF FUNCTION
N = 122
CAND N = N + 1
DS = DIGSET.(N)
THROUGH MUL, FOR M=2, 1, M.G.6
MUL WHENEVER DIGSET.(N*M).NE.DS, TRANSFER TO CAND
THROUGH SHOW, FOR M=1, 1, M.G.6
SHOW PRINT FORMAT FMT, M, N*M
END OF PROGRAM</syntaxhighlight>
{{out}}
<pre>1 * N = 142857
2 * N = 285714
3 * N = 428571
4 * N = 571428
5 * N = 714285
6 * N = 857142</pre>
 
=={{header|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).
 
<langsyntaxhighlight Nimlang="nim">from algorithm import sorted
 
func search(): int =
Line 385 ⟶ 661:
echo " n = ", n
for k in 2..6:
echo k, "n = ", k * n</langsyntaxhighlight>
 
{{out}}
Line 394 ⟶ 670:
5n = 714285
6n = 857142</pre>
 
=={{header|Pascal}}==
Create an array of the digits fixed 1 as first digit and 0 "1023456789"<BR>
Line 399 ⟶ 676:
Using set of tdigit ,so no sort of digits is required.<BR>
Don't use the fact, that second digit must be < 6.Runtime negligible.<BR>
<langsyntaxhighlight lang="pascal">program euler52;
{$IFDEF FPC}
{$MOde DElphi} {$Optimization On,ALL}
Line 561 ⟶ 838:
readln;
{$ENDIF}
end.</langsyntaxhighlight>
{{out}}
<pre>TIO.RUN
Line 608 ⟶ 885:
 
=={{header|Perl}}==
<langsyntaxhighlight lang="perl">#!/usr/bin/perl
 
use strict; # https://rosettacode.org/wiki/Permuted_multiples
Line 624 ⟶ 901:
};
printf " n %s\n", $n;
printf "%dn %s\n", $_ , $n * $_ for 2 .. 6;</langsyntaxhighlight>
{{out}}
<pre>
Line 637 ⟶ 914:
=={{header|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.
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
Line 677 ⟶ 954:
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 771 ⟶ 1,048:
</pre>
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.
 
=={{header|Quackery}}==
 
<syntaxhighlight lang="Quackery"> [ [] swap
[ 10 /mod
rot join swap
dup 0 = until ]
drop ] is digits ( n --> [ )
 
[ true swap
dup digits sort
swap
5 times
[ dup i 2 + *
digits sort
dip over != if
[ rot not unrot
conclude ] ]
2drop ] is permult ( n --> b )
 
0
[ 1+
dup permult until ]
6 times
[ dup
i^ 1+ dup echo
say " * n = "
* echo cr ]
drop</syntaxhighlight>
 
{{out}}
 
<pre>1 * n = 142857
2 * n = 285714
3 * n = 428571
4 * n = 571428
5 * n = 714285
6 * n = 857142</pre>
 
=={{header|Raku}}==
<syntaxhighlight lang="raku" perl6line>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×$_}" } }</langsyntaxhighlight>
{{out}}
<pre> n: 142857
Line 786 ⟶ 1,101:
 
=={{header|REXX}}==
<langsyntaxhighlight 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.*/
Line 814 ⟶ 1,129:
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 ?</langsyntaxhighlight>
{{out|output|text=&nbsp; when using the internal default input:}}
<pre>
Line 826 ⟶ 1,141:
 
=={{header|Ring}}==
<langsyntaxhighlight lang="ring">
load "stdlib.ring"
 
Line 864 ⟶ 1,179:
 
see "done..." + nl
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 879 ⟶ 1,194:
 
=={{header|Swift}}==
<langsyntaxhighlight lang="swift">func getDigits(_ num: Int) -> Array<Int> {
var n = num
var digits = Array(repeating: 0, count: 10)
Line 915 ⟶ 1,230:
}
p *= 10
}</langsyntaxhighlight>
 
{{out}}
Line 930 ⟶ 1,245:
{{libheader|Wren-math}}
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.
<langsyntaxhighlight ecmascriptlang="wren">import "./math" for Int
 
// assumes l1 is sorted but l2 is not
Line 968 ⟶ 1,283:
}
i = i + 1
}</langsyntaxhighlight>
 
{{out}}
Line 983 ⟶ 1,298:
 
=={{header|XPL0}}==
<langsyntaxhighlight XPL0lang="xpl0">func Digits(N); \Return counts of digits packed in 30 bits
int N, Sums;
[Sums:= 0;
Line 1,003 ⟶ 1,318:
];
IntOut(0, N);
]</langsyntaxhighlight>
 
{{out}}
PureFox
9,476

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/315149...355011"