N-smooth numbers: Difference between revisions

Content added Content deleted
(qualify task requirements [“calculate”] otherwise a few `printf` would be sufficient, →‎Pascal: standardize [use language as per ISO specifications], resolve {{incorrect}}])
Line 23: Line 23:


;Task:
;Task:
:*   show the first   '''25'''   n-smooth numbers   for   '''n=2'''   ───►   '''n=29'''
:*   calculate and show the first   '''25'''   n-smooth numbers   for   '''n=2'''   ───►   '''n=29'''
:*   show   three numbers starting with   '''3,000'''   n-smooth numbers   for   '''n=3'''   ───►   '''n=29'''
:*   calculate and show   three numbers starting with   '''3,000'''   n-smooth numbers   for   '''n=3'''   ───►   '''n=29'''
:*   show twenty numbers starting with  '''30,000'''   n-smooth numbers   for   '''n=503'''   ───►   '''n=521'''   (optional)
:*   calculate and show twenty numbers starting with  '''30,000'''   n-smooth numbers   for   '''n=503'''   ───►   '''n=521'''   (optional)




Line 2,349: Line 2,349:


=={{header|Pascal}}==
=={{header|Pascal}}==
{{works with|Extended Pascal}}
<lang Pascal>program nSmoothNumbers(output);


const
{{incorrect|Pascal| <br><br> for the 2<sup>nd</sup> part of the task, <br> starting at three thousand, <br> '''n'''-smooth for '''3''' and '''5''' aren't displayed. <br><br>}}
primeCount = 538;
{$ifDef __GPC__} {$setLimit=3889} {$endIf}
cardinalMax = 3888;


{{works with|Free Pascal}} 64-Bit.
Using trail-division with the first primes.Takes too long for first 3 after 2999 2,3,5-smooth numbers.
<lang Pascal>program HammNumb;
{$IFDEF FPC}
{$MODE DELPHI}
{$OPTIMIZATION ON,ALL}
{$ELSE}
{$APPTYPE CONSOLE}
{$ENDIF}
type
type
cardinal = 0..cardinalMax;
tHamNum = record
cardinals = set of cardinal;
hampot : array[0..167] of Word;
cardinalPositive = 1..cardinalMax;
hampotmax,
hamNum : NativeUint;
natural = 1..maxInt;
end;

primeIndex = 1..primeCount;
const
primes : array[0..167] of word =
list = array[primeIndex] of cardinal;
(2, 3, 5, 7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71
,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151
,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233
,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317
,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419
,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503
,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607
,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701
,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811
,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911
,919,929,937,941,947,953,967,971,977,983,991,997);


var
var
prime: list;
HNum:tHamNum;


{
procedure OutHamNum(const HNum:tHamNum);
\brief performs prime factorization
\param n the number to factorize
\return list of exponents for a unique integer factorization using primes
This function requires the global `prime` variable to be initialized.
}
function primeFactorization(n: natural): list;
var
var
i : NativeInt;
i: primeIndex;
{
Begin
Instead of writing `[1: 0; 2: 0; 3: 0; …]`, Extended Pascal permits us
with Hnum do
to use an “array completer” for all unspecified values.
Begin
}
write(hamNum:12,' : ');
result: list value [otherwise 0];
For i := 0 to hampotmax-1 do
begin
write(primes[i],'^',hampot[i],'*');
for i := 1 to primeCount do
writeln(primes[hampotmax],'^',hampot[hampotmax]);
begin
end;
while n mod prime[i] = 0 do
begin
n := n div prime[i];
result[i] := result[i] + 1
end
end;
{ Nullify result if the utilized `prime` list was insufficient. }
if n <> 1 then
begin
{ `array` literals need an explicit data type specification. }
result := list[otherwise 0]
end;
{
In a Pascal function definition there must be _one_ assignment to the
(implicitly) declared variable bearing the same name as of the function.
This will be returned function result.
}
primeFactorization := result
end;
end;


{
procedure NextHammNum(var HNum:tHamNum;maxP:NativeInt);
\brief returns whether a number is an n-smooth number
\param smoothness the maximum permissible prime factor
\param x the number to check
\return whether \param x is smoothness-smooth
}
function isSmooth(
protected smoothness: cardinalPositive;
protected x: natural
): Boolean;
{
Return set of non-one factors (i.e. non-zero exponent).
Nesting this function permits most compilers to allocate memory
for variables only if the function is actually needed.
}
function factorizationBases: cardinals;
var
exponent: list;
i: primeIndex;
result: cardinals value [];
begin
exponent := primeFactorization(x);
for i := 1 to primeCount do
begin
if exponent[i] > 0 then
begin
result := result + [prime[i]]
end
end;
factorizationBases := result
end;
begin
case smoothness of
1:
begin
{
The value `1` actually does not have a prime factorization, yet as per
task specification “1 (unity) is always included in n‑smooth numbers.”
}
isSmooth := x = 1
end;
{ 2‑smooth numbers is an alias for powers of 2 (OEIS sequence A000079) }
2:
begin
isSmooth := 2 pow round(ln(x) / ln(2)) = x
end
{ The `otherwise` catch-all-clause is an Extended Pascal extension. }
otherwise
begin
isSmooth := card(factorizationBases - [0..smoothness]) = 0
{
`card` (“cardinality”) is an Extended Pascal extension.
Testing `card(M) = 0` is equivalent to `M = []` (empty set).
}
end
end
end;

{ === ancillary routines =============================================== }

{ This is just your regular Eratosthenes prime sieve. }
procedure sieve(var primes: cardinals);
var
var
n: natural;
q,p,nr,n,pnum,momPrime : NativeUInt;
i: integer;
multiples: cardinals;
begin
begin
{ `1` is by definition not a prime number }
n := HNum.hamNum;
primes := primes - [1];
repeat
inc(n);
{ find the next non-crossed number }
nr := n;
for n := 2 to cardinalMax do
//check divisibility by first (count=maxP) primes
begin
pnum := 0;
if n in primes then
repeat
begin
momPrime := primes[pnum];
multiples := [];
q := nr div momPrime;
{ We do _not_ want to remove 1 * n. }
p := 0;
i := 2 * n;
while q*momPrime=nr do
while i in [n..cardinalMax] do
Begin
begin
inc(p);
multiples := multiples + [i];
nr := q;
q := nr div momPrime;
i := i + n
end;
end;
HNum.hampot[pnum] := p;
primes := primes - multiples
inc(pnum);
end
until (nr=1) OR (pnum > maxp)
end
//finished ?
until nr = 1;

With HNum do
Begin
hamNum := n;
hamPotmax := pnum-1;
end;
end;
end;


{ This procedure transforms a `set` to an `array`. }
procedure OutXafterYSmooth(X,Y,SmoothIdx: NativeUInt);
procedure populatePrime;
var
var
primes: cardinals value [1..cardinalMax];
i: NativeUint;
n: natural value 1;
i: primeIndex value 1;
begin
begin
IF SmoothIdx> High(primes) then
sieve(primes);
EXIT;
for i := 1 to primeCount do
HNum.HamNum := 0;
begin
dec(Y);
repeat
for i := 1 to Y do
begin
NextHammNum(HNum,SmoothIdx);
n := n + 1
write('first ',X,' after ',Y,' ',primes[SmoothIdx]:3,'-smooth numbers : ');
end
for i := 1 to X do
until n in primes;
begin
NextHammNum(HNum,SmoothIdx);
prime[i] := n
write(HNum.HamNum,' ');
end;
end
writeln;
end;
end;


{ ### MAIN ############################################################# }
var
var
i: primeIndex value primeCount;
j: NativeUint;
candidate: natural;
Begin
count: cardinal;
j := 0;
begin
while primes[j] <= 29 do
populatePrime;
Begin
OutXafterYSmooth(25,1,j);
{ Show the first 25 n-smooth numbers […] }
inc(j);
{ […] only prime [n] are to be used. }
end;
while prime[i] > 29 do
writeln;
begin
i := i - 1
end;
{
In Pascal, `for` loop limits are evaluated _once_,
so this is perfectly legal:
}
for i := 1 to i do
begin
write(prime[i]:4, '-smooth: 1');
count := 1; { `1` already listed. }
candidate := 2;
while count < 25 do
begin
if isSmooth(prime[i], candidate) then
begin
write(', ', candidate:1);
count := count + 1
end;
candidate := candidate + 1
end;
writeLn
end;
{
Note, in Pascal, the `for`‑loop iteration variable is not modified.
At this point in the code, `i` (still) has the value after the `while`-loop.
[This statement is not true, if a `goto` prematurely exited the `for`‑loop.]
}
writeLn;
{ […] show three numbers starting with 3,000 […] }
for i := 2 to i do
begin
write(prime[i]:4, '-smooth:');
count := 0;
candidate := 3000;
while count < 3 do
begin
if isSmooth(prime[i], candidate) then
begin
write(' ', candidate:1);
count := count + 1
end;
candidate := candidate + 1
end;
writeLn
end;
end.</lang>
{{out}}
<pre style="height:45ex"> 2-smooth: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216
3-smooth: 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81, 96, 108, 128, 144, 162, 192
5-smooth: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54
7-smooth: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, 28, 30, 32, 35, 36
11-smooth: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 27, 28, 30, 32
13-smooth: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28
17-smooth: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20, 21, 22, 24, 25, 26, 27
19-smooth: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 25, 26
23-smooth: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25
29-smooth: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25


3-smooth: 3072 3456 3888
j := 3;
5-smooth: 3000 3072 3125
while primes[j] <= 29 do
7-smooth: 3000 3024 3072
Begin
11-smooth: 3000 3024 3025
OutXafterYSmooth(3,3000,j);
13-smooth: 3000 3003 3024
inc(j);
17-smooth: 3000 3003 3024
end;
19-smooth: 3000 3003 3024
writeln;
23-smooth: 3000 3003 3024
while primes[j] < 503 do
29-smooth: 3000 3003 3016</pre>
inc(j);
while primes[j] <= 521 do
Begin
OutXafterYSmooth(20,30000,j);
inc(j);
end;
writeln;
End.</lang>{{out}}<pre>first 25 after 0 2-smooth numbers : 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216
first 25 after 0 3-smooth numbers : 1 2 3 4 6 8 9 12 16 18 24 27 32 36 48 54 64 72 81 96 108 128 144 162 192
first 25 after 0 5-smooth numbers : 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50 54
first 25 after 0 7-smooth numbers : 1 2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27 28 30 32 35 36
first 25 after 0 11-smooth numbers : 1 2 3 4 5 6 7 8 9 10 11 12 14 15 16 18 20 21 22 24 25 27 28 30 32
first 25 after 0 13-smooth numbers : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 20 21 22 24 25 26 27 28
first 25 after 0 17-smooth numbers : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20 21 22 24 25 26 27
first 25 after 0 19-smooth numbers : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 24 25 26
first 25 after 0 23-smooth numbers : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
first 25 after 0 29-smooth numbers : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

first 3 after 2999 7-smooth numbers : 50176000 50331648 50388480
first 3 after 2999 11-smooth numbers : 2112880 2116800 2117016
first 3 after 2999 13-smooth numbers : 390000 390390 390625
first 3 after 2999 17-smooth numbers : 145800 145860 146016
first 3 after 2999 19-smooth numbers : 74256 74358 74360
first 3 after 2999 23-smooth numbers : 46552 46575 46585
first 3 after 2999 29-smooth numbers : 33516 33524 33534

first 20 after 29999 503-smooth numbers : 62913 62914 62916 62918 62920 62923 62926 62928 62930 62933 62935 62937 62944 62946 62951 62952 62953 62957 62959 62964
first 20 after 29999 509-smooth numbers : 62601 62602 62604 62607 62608 62609 62611 62618 62620 62622 62624 62625 62626 62628 62629 62634 62640 62643 62645 62646
first 20 after 29999 521-smooth numbers : 62287 62288 62291 62292 62300 62304 62307 62308 62310 62315 62320 62321 62322 62325 62328 62329 62330 62331 62335 62336

real 0m2,665s
user 0m2,655s
sys 0m0,003s
</pre>


=={{header|Perl}}==
=={{header|Perl}}==
Retrieved from "https://rosettacode.org/wiki/N-smooth_numbers"