Humble numbers
Humble numbers are positive integers which have no prime facters > 7.
Humble numbers are also called 7-smooth numbers, and sometimes called highly composite,
although this conflicts with another meaning of highly composite numbers.
Another way to express the above is:
humble = 2i × 3j × 5k × 7m
where i, j, k, m ≥ 0
- Task
-
- show the first 50 humble numbers (in a horizontal list)
- show the number of humble numbers that have x decimal digits for all x's up to n (inclusive).
- show (as many as feasible or reasonable for above) on separate lines
- show all output here on this page
- Related tasks
- References
Factor
<lang factor>USING: accessors assocs combinators deques dlists formatting fry generalizations io kernel make math math.functions math.order prettyprint sequences tools.memory.private ; IN: rosetta-code.humble-numbers
TUPLE: humble-iterator 2s 3s 5s 7s digits ;
- <humble-iterator> ( -- humble-iterator )
humble-iterator new
1 1dlist >>2s
1 1dlist >>3s
1 1dlist >>5s
1 1dlist >>7s
H{ } clone >>digits ;
- enqueue ( n humble-iterator -- )
{
[ [ 2 * ] [ 2s>> ] ]
[ [ 3 * ] [ 3s>> ] ]
[ [ 5 * ] [ 5s>> ] ]
[ [ 7 * ] [ 7s>> ] ]
} [ bi* push-back ] map-compose 2cleave ;
- count-digits ( humble-iterator n -- )
[ 1 ] 2dip log10 1 + >integer swap digits>> at+ ;
- ?pop ( 2s 3s 5s 7s n -- )
'[ dup peek-front _ = [ pop-front* ] [ drop ] if ] 4 napply ;
- next ( humble-iterator -- n )
dup dup { [ 2s>> ] [ 3s>> ] [ 5s>> ] [ 7s>> ] } cleave
4 ndup [ peek-front ] 4 napply min min min
{ [ ?pop ] [ swap enqueue ] [ count-digits ] [ ] } cleave ;
- upto-n-digits ( humble-iterator n -- seq )
1 + swap [ [ 2dup digits>> key? ] [ dup next , ] until ] { }
make [ digits>> delete-at ] dip but-last-slice ;
- .first50 ( seq -- )
"First 50 humble numbers:" print 50 head [ pprint bl ] each nl ;
- .digit-breakdown ( humble-iterator -- )
"The digit counts of humble numbers:" print digits>> [
commas swap dup 1 = "" "s" ? "%9s have %2d digit%s\n"
printf
] assoc-each ;
- humble-numbers ( -- )
<humble-iterator> dup 80 upto-n-digits
[ .first50 nl ] [ drop .digit-breakdown nl ] [
"Total number of humble numbers found: " write length
commas print
] tri ;
MAIN: humble-numbers</lang>
- Output:
First 50 humble 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 40 42 45 48 49 50 54 56 60 63 64 70 72 75 80 81 84 90 96 98 100 105 108 112 120
The digit counts of humble numbers:
9 have 1 digit
36 have 2 digits
95 have 3 digits
197 have 4 digits
356 have 5 digits
579 have 6 digits
882 have 7 digits
1,272 have 8 digits
1,767 have 9 digits
2,381 have 10 digits
3,113 have 11 digits
3,984 have 12 digits
5,002 have 13 digits
6,187 have 14 digits
7,545 have 15 digits
9,081 have 16 digits
10,815 have 17 digits
12,759 have 18 digits
14,927 have 19 digits
17,323 have 20 digits
19,960 have 21 digits
22,853 have 22 digits
26,015 have 23 digits
29,458 have 24 digits
33,188 have 25 digits
37,222 have 26 digits
41,568 have 27 digits
46,245 have 28 digits
51,254 have 29 digits
56,618 have 30 digits
62,338 have 31 digits
68,437 have 32 digits
74,917 have 33 digits
81,793 have 34 digits
89,083 have 35 digits
96,786 have 36 digits
104,926 have 37 digits
113,511 have 38 digits
122,546 have 39 digits
132,054 have 40 digits
142,038 have 41 digits
152,515 have 42 digits
163,497 have 43 digits
174,986 have 44 digits
187,004 have 45 digits
199,565 have 46 digits
212,675 have 47 digits
226,346 have 48 digits
240,590 have 49 digits
255,415 have 50 digits
270,843 have 51 digits
286,880 have 52 digits
303,533 have 53 digits
320,821 have 54 digits
338,750 have 55 digits
357,343 have 56 digits
376,599 have 57 digits
396,533 have 58 digits
417,160 have 59 digits
438,492 have 60 digits
460,533 have 61 digits
483,307 have 62 digits
506,820 have 63 digits
531,076 have 64 digits
556,104 have 65 digits
581,902 have 66 digits
608,483 have 67 digits
635,864 have 68 digits
664,053 have 69 digits
693,065 have 70 digits
722,911 have 71 digits
753,593 have 72 digits
785,141 have 73 digits
817,554 have 74 digits
850,847 have 75 digits
885,037 have 76 digits
920,120 have 77 digits
956,120 have 78 digits
993,058 have 79 digits
1,030,928 have 80 digits
Total number of humble numbers found: 21,307,183
Go
Not very fast and uses a lot of memory but easier to understand than the 'log' based methods for generating 7-smooth numbers. <lang go>package main
import (
"fmt" "math/big"
)
var (
one = new(big.Int).SetUint64(1) two = new(big.Int).SetUint64(2) three = new(big.Int).SetUint64(3) five = new(big.Int).SetUint64(5) seven = new(big.Int).SetUint64(7)
)
func min(a, b *big.Int) *big.Int {
if a.Cmp(b) < 0 {
return a
}
return b
}
func humble(n int) []*big.Int {
h := make([]*big.Int, n)
h[0] = new(big.Int).Set(one)
next2, next3 := new(big.Int).Set(two), new(big.Int).Set(three)
next5, next7 := new(big.Int).Set(five), new(big.Int).Set(seven)
var i, j, k, l int
for m := 1; m < len(h); m++ {
h[m] = new(big.Int).Set(min(next2, min(next3, min(next5, next7))))
if h[m].Cmp(next2) == 0 {
i++
next2.Mul(two, h[i])
}
if h[m].Cmp(next3) == 0 {
j++
next3.Mul(three, h[j])
}
if h[m].Cmp(next5) == 0 {
k++
next5.Mul(five, h[k])
}
if h[m].Cmp(next7) == 0 {
l++
next7.Mul(seven, h[l])
}
}
return h
}
func commatize(n int) string {
s := fmt.Sprintf("%d", n)
le := len(s)
for i := le - 3; i >= 1; i -= 3 {
s = s[0:i] + "," + s[i:]
}
return s
}
func main() {
const n = 13 * 1e6 // calculate the first 13 million humble numbers, say
h := humble(n)
fmt.Println("The first 50 humble numbers are:")
fmt.Println(h[0:50])
maxDigits := len(h[len(h)-1].String()) - 1
counts := make([]int, maxDigits+1)
var maxUsed int
for i := 0; i < len(h); i++ {
digits := len(h[i].String())
if digits > maxDigits {
maxUsed = i
break
}
counts[digits]++
}
fmt.Printf("\nOf the first %s humble numbers:\n", commatize(maxUsed))
for i := 1; i <= maxDigits; i++ {
s := "s"
if i == 1 {
s = ""
}
fmt.Printf("%9s have %2d digit%s\n", commatize(counts[i]), i, s)
}
}</lang>
- Output:
The first 50 humble numbers are:
[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 40 42 45 48 49 50 54 56 60 63 64 70 72 75 80 81 84 90 96 98 100 105 108 112 120]
Of the first 12,591,874 humble numbers:
9 have 1 digit
36 have 2 digits
95 have 3 digits
197 have 4 digits
356 have 5 digits
579 have 6 digits
882 have 7 digits
1,272 have 8 digits
1,767 have 9 digits
2,381 have 10 digits
3,113 have 11 digits
3,984 have 12 digits
5,002 have 13 digits
6,187 have 14 digits
7,545 have 15 digits
9,081 have 16 digits
10,815 have 17 digits
12,759 have 18 digits
14,927 have 19 digits
17,323 have 20 digits
19,960 have 21 digits
22,853 have 22 digits
26,015 have 23 digits
29,458 have 24 digits
33,188 have 25 digits
37,222 have 26 digits
41,568 have 27 digits
46,245 have 28 digits
51,254 have 29 digits
56,618 have 30 digits
62,338 have 31 digits
68,437 have 32 digits
74,917 have 33 digits
81,793 have 34 digits
89,083 have 35 digits
96,786 have 36 digits
104,926 have 37 digits
113,511 have 38 digits
122,546 have 39 digits
132,054 have 40 digits
142,038 have 41 digits
152,515 have 42 digits
163,497 have 43 digits
174,986 have 44 digits
187,004 have 45 digits
199,565 have 46 digits
212,675 have 47 digits
226,346 have 48 digits
240,590 have 49 digits
255,415 have 50 digits
270,843 have 51 digits
286,880 have 52 digits
303,533 have 53 digits
320,821 have 54 digits
338,750 have 55 digits
357,343 have 56 digits
376,599 have 57 digits
396,533 have 58 digits
417,160 have 59 digits
438,492 have 60 digits
460,533 have 61 digits
483,307 have 62 digits
506,820 have 63 digits
531,076 have 64 digits
556,104 have 65 digits
581,902 have 66 digits
608,483 have 67 digits
635,864 have 68 digits
664,053 have 69 digits
693,065 have 70 digits
REXX
<lang rexx>/*REXX program computes and displays humble numbers, also will display counts of sizes.*/ parse arg n m . /*obtain optional arguments from the CL*/ if n== | n=="," then n= 50 /*Not specified? Then use the default.*/ if m== | m=="," then m= 60 /* " " " " " " */ numeric digits 1 + max(20, m) /*be able to handle some big numbers. */ $.= 0 /*a count array for X digit humble #s*/ call humble n; list= /*call HUMBLE sub; initialize the list.*/
do j=1 for n; list= list @.j /*append a humble number to the list.*/
end /*j*/
if list\= then do; say "A list of the first " n ' humble numbers are:'
say strip(list) /*elide the leading blank in the list. */
end
say call humble -m /*invoke subroutine for counting nums. */ if $.1==0 then exit /*if no counts, then we're all finished*/ total= 0 /*initialize count of humble numbers. */ $.1= $.1 + 1 /*adjust count for absent 1st humble #.*/ say ' The digit counts of humble numbers:' say ' ═════════════════════════════════════════'
do c=1 while $.c>0; s= left('s', length($.c)>1) /*count needs pluralization?*/
say right( commas($.c), 30) ' have ' right(c, 2) " digit"s
total= total + $.c /* ◄─────────────────────────────────┐ */
end /*k*/ /*bump humble number count (so far)──┘ */
/*REXX program computes and displays humble numbers, also will display a count of sizes.*/ exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: procedure; arg _; do i=length(_)-3 to 1 by -3; _=insert(',', _, i); end; return _ /*──────────────────────────────────────────────────────────────────────────────────────*/ humble: procedure expose @. $.; parse arg x; if x==0 then return
y= abs(x); a= y; noCount= x>0; if x<0 then y= 999999999
#2= 1; #3= 1; #5= 1; #7= 1 /*define the initial humble constants. */
$.= 0; @.= 0; @.1= 1 /*initialize counts and humble numbers.*/
do h=2 for y-1
@.h= min(2*@.#2,3*@.#3,5*@.#5,7*@.#7) /*pick the minimum of 4 humble numbers.*/
m= @.h /*M: " " " " " " */
if 2*@.#2 == m then #2 = #2 + 1 /*Is number already defined? Use next #*/
if 3*@.#3 == m then #3 = #3 + 1 /* " " " " " " "*/
if 5*@.#5 == m then #5 = #5 + 1 /* " " " " " " "*/
if 7*@.#7 == m then #7 = #7 + 1 /* " " " " " " "*/
if noCount then iterate /*Not counting digits? Then iterate. */
L= length(m); if L>a then leave /*Are we done with counting? Then quit*/
$.L= $.L + 1 /*bump the digit count for this number.*/
end /*h*/ /*the humble numbers are in the @ array*/
return /* " count results " " " $ " */</lang>
- output when using the default inputs:
A list of the first 50 humble numbers are:
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 40 42 45 48 49 50 54 56 60 63 64 70 72 75 80 81 84 90 96 98 100 105 108 112 120
The digit counts of humble numbers:
═════════════════════════════════════════
9 have 1 digit
36 have 2 digits
95 have 3 digits
197 have 4 digits
356 have 5 digits
579 have 6 digits
882 have 7 digits
1,272 have 8 digits
1,767 have 9 digits
2,381 have 10 digits
3,113 have 11 digits
3,984 have 12 digits
5,002 have 13 digits
6,187 have 14 digits
7,545 have 15 digits
9,081 have 16 digits
10,815 have 17 digits
12,759 have 18 digits
14,927 have 19 digits
17,323 have 20 digits
19,960 have 21 digits
22,853 have 22 digits
26,015 have 23 digits
29,458 have 24 digits
33,188 have 25 digits
37,222 have 26 digits
41,568 have 27 digits
46,245 have 28 digits
51,254 have 29 digits
56,618 have 30 digits
62,338 have 31 digits
68,437 have 32 digits
74,917 have 33 digits
81,793 have 34 digits
89,083 have 35 digits
96,786 have 36 digits
104,926 have 37 digits
113,511 have 38 digits
122,546 have 39 digits
132,054 have 40 digits
142,038 have 41 digits
152,515 have 42 digits
163,497 have 43 digits
174,986 have 44 digits
187,004 have 45 digits
199,565 have 46 digits
212,675 have 47 digits
226,346 have 48 digits
240,590 have 49 digits
255,415 have 50 digits
270,843 have 51 digits
286,880 have 52 digits
303,533 have 53 digits
320,821 have 54 digits
338,750 have 55 digits
357,343 have 56 digits
376,599 have 57 digits
396,533 have 58 digits
417,160 have 59 digits
438,492 have 60 digits
total number of humble numbers found: 6,870,667