N-smooth numbers
n-smooth numbers are positive integers which have no prime factors > n.
The n (when using it in the expression n-smooth is always prime,
there are no 9-smooth numbers.
1 (unity) is always included in n-smooth numbers.
2-smooth numbers are non-negative powers of two.
5-smooth numbers are also called Hamming numbers.
7-smooth numbers are also called humble numbers.
A way to express 11-smooth numbers is:
11-smooth = 2i × 3j × 5k × 7m × 11p
where i, j, k, m, p ≥ 0
- Task
-
- 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
- show twenty numbers starting with 30,000 n-smooth numbers for n=503 ───► n=521 (optional)
All ranges (for n) are to be inclusive, and only prime numbers are to be used.
The (optional) n-smooth numbers for the third range are: 503, 509, and 521.
Show all n-smooth numbers for any particular n in a horizontal list.
Show all output here on this page.
- Related tasks
- References
-
- Wikipedia: [wp:Smooth number|smooth number]
- OEIS: 5-smooth or Hamming numbers
- OEIS: 7-smooth or humble numbers
<lang rexx>/*REXX program computes & displays X n-smooth numbers; both X and N can be specified.*/ numeric digits 200 /*be able to handle some big numbers. */ parse arg LOx HIx LOn HIn . /*obtain optional arguments from the CL*/ if LOx== | LOx=="," then LOx= 1 /*Not specified? Then use the default.*/ if HIx== | HIx=="," then HIx= LOx + 19 /* " " " " " " */ if LOn== | LOn=="," then LOn= 2 /* " " " " " " */ if HIn== | HIn=="," then HIn= LOn + 27 /* " " " " " " */ call genP HIn /*generate enough primes to satisfy HIn*/ @aList= ' a list of the '; @thru= ' through ' /*literals used with a SAY.*/
do j=LOn to HIn; if !.j==0 then iterate /*if not prime, then skip this number. */
call smooth HIx,j; $= /*invoke SMOOTH; initialize $ (list). */
do k=LOx to HIx; $= $ #.k /*append a smooth number to " " " */
end /*k*/
say center(@aList th(LOx) @thru th(HIx) ' numbers for' j"-smooth ", 130, "═")
say strip($); say
end /*j*/ /* [↑] the $ list has a leading blank.*/
exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ genP: procedure expose @. !. #; parse arg x /*#≡num of primes; @. ≡array of primes.*/
@.=; @.1=2; @.2=3; @.3=5; @.4=7; @.5=11; @.6=13; @.7=17; @.8=19; @.9=23; #=9
!.=0; !.2=1; !.3=2; !.5=3; !.7=4; !.11=5; !.13=6; !.17=7; !.19=8; !.23=9
do k=@.#+4 by 2 until #>=x ; if k//3==0 then iterate
parse var k -1 _; if _==5 then iterate
do d=4 until @.d**2>k; if k//@.d==0 then iterate k
end /*d*/
#= # + 1; !.k= k; @.#= k /*found a prime, bump counter; assign @*/
end /*k*/; return
/*──────────────────────────────────────────────────────────────────────────────────────*/ smooth: procedure expose @. !. #.; parse arg y,p /*obtain the arguments from the invoker*/
if p== then p= 3 /*Not specified? Then assume Hamming #s*/
n= !.p /*the number of primes being used. */
nn= n - 1; #.= 0; #.1= 1 /*an array of n-smooth numbers (so far)*/
f.= 1 /*the indices of factors of a number. */
do j=2 for y-1; _= f.1
z= @.1 * #._
do k=2 for nn; _= f.k; v= @.k * #._; if v<z then z= v
end /*k*/
#.j= z
do d=1 for n; _= f.d; if @.d * #._==z then f.d= f.d + 1
end /*d*/
end /*j*/; return
/*──────────────────────────────────────────────────────────────────────────────────────*/ th: parse arg th; return th || word('th st nd rd', 1+(th//10)*(th//100%10\==1)*(th//10<4))</lang>
- output when using the default inputs:
════════════════════════════════════ a list of the 1st through 25th numbers for 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 ════════════════════════════════════ a list of the 1st through 25th numbers for 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 ════════════════════════════════════ a list of the 1st through 25th numbers for 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 ════════════════════════════════════ a list of the 1st through 25th numbers for 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 ════════════════════════════════════ a list of the 1st through 25th numbers for 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 ════════════════════════════════════ a list of the 1st through 25th numbers for 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 ════════════════════════════════════ a list of the 1st through 25th numbers for 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 ════════════════════════════════════ a list of the 1st through 25th numbers for 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 ════════════════════════════════════ a list of the 1st through 25th numbers for 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 ════════════════════════════════════ a list of the 1st through 25th numbers for 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
- output when using the input of: 30000 30019 503 521
════════════════════════════════ a list of the 30000th through 30019th numbers for 503-smooth ════════════════════════════════ 38120 38121 38122 38123 38124 38125 38126 38127 38128 38129 38130 38131 38133 38134 38135 38136 38137 38140 38141 38142 ════════════════════════════════ a list of the 30000th through 30019th numbers for 509-smooth ════════════════════════════════ 38036 38037 38038 38040 38041 38042 38043 38045 38046 38048 38049 38050 38051 38052 38054 38055 38056 38057 38060 38063 ════════════════════════════════ a list of the 30000th through 30019th numbers for 521-smooth ════════════════════════════════ 37859 37860 37862 37863 37867 37869 37870 37872 37873 37874 37875 37876 37877 37878 37880 37881 37882 37883 37884 37886