Humble numbers: Difference between revisions
→{{header|Wren}}: Tidy
GordonBGood (talk | contribs) (→{{header|F_Sharp|F#}}: added Elm contribution above...) |
(→{{header|Wren}}: Tidy) |
||
| (6 intermediate revisions by 4 users not shown) | |||
Line 492:
1767 9
</pre>
=={{header|BBC BASIC}}==
{{works with|BBC BASIC for Windows}}
<syntaxhighlight lang="bbcbasic"> MaxDigs%=8
DIM Humble%(MaxDigs% - 1)
I%=1
@%=4
PRINT "The first 50 humble numbers:"
WHILE TRUE
IF FNIsHumble(I%) THEN
IF C% < 50 PRINT ;I% " ";
C%+=1
S%=LENSTR$I%
IF S% > MaxDigs% EXIT WHILE
Humble%(S%-1)+=1
ENDIF
I%+=1
ENDWHILE
PRINT ''"Of the first ";C% " humble numbers:"
FOR I%=0 TO MaxDigs% - 1
PRINT Humble%(I%) " have ";I% + 1 LEFT$(" digits", I% + 6)
NEXT
END
DEF FNIsHumble(i%)
IF i% <= 1 THEN =TRUE
IF i% MOD 2 == 0 THEN =FNIsHumble(i% / 2)
IF i% MOD 3 == 0 THEN =FNIsHumble(i% / 3)
IF i% MOD 5 == 0 THEN =FNIsHumble(i% / 5)
IF i% MOD 7 == 0 THEN =FNIsHumble(i% / 7)
=FALSE</syntaxhighlight>
{{out}}
<pre>The 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
Of the first 3427 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
1272 have 8 digits</pre>
=={{header|C}}==
Line 2,295 ⟶ 2,341:
=={{header|Delphi}}==
See [https://rosettacode.org/wiki/Humble_numbers#Pascal Pascal].
=={{header|EasyLang}}==
<syntaxhighlight>
fastfunc humble i .
if i <= 1
return 1
.
if i mod 2 = 0
return humble (i / 2)
.
if i mod 3 = 0
return humble (i / 3)
.
if i mod 5 = 0
return humble (i / 5)
.
if i mod 7 = 0
return humble (i / 7)
.
return 0
.
fastfunc next_humble n .
repeat
n += 1
until humble n = 1
.
return n
.
len arr[] 9
while cnt < 5193
n = next_humble n
arr[log10 n + 1] += 1
cnt += 1
if cnt <= 50
write n & " "
.
.
print ""
print ""
for i to 9
print arr[i] & " with " & i & " digits"
.
</syntaxhighlight>
{{out}}
<pre>
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
9 with 1 digits
36 with 2 digits
95 with 3 digits
197 with 4 digits
356 with 5 digits
579 with 6 digits
882 with 7 digits
1272 with 8 digits
1767 with 9 digits
</pre>
=={{header|Elm}}==
Line 2,561 ⟶ 2,664:
There are 12759 humble numbers with 18 digits
</pre>
===Faster by Using Less Seq's and Using Logarithmic Approximations for Ordering===
The above code is somewhat of a "toy" implementation in that it is very obscure and difficult to read and understand, even for someone used to F# and functional programming using closures (come now, spell your name with the names of the functions???). The above code is also very slow and therefore limited, even if the minor changes so that it outputs BigInt's is done; this is due to overuse of the very slow Seq's for iteration and the deeply nested closure functions which don't implement memoization other than for the equivalent heads of the "lazy lists" and therefore repeat many operations and thus don't have a linear response with number of elements (which also would not be linear due to the increasing amount of work in doing BigInt computations). The following code doesn't use Seq' but rather a "roll-your-own" Co-Inductive Stream (CIS) and eliminates the need for memoization by keeping track of the required back results in DotNet Queue's; it also uses a logarithmic representation for ordering comparisons to eliminate the BigInt operations:
<syntaxhighlight lang="fsharp">// a count and logarithmic approximation of the humble value...
type LogRep = struct val lg: uint64; val x2: uint16; val x3: uint16;
val x5: uint16; val x7: uint16
new(lg, x2, x3, x5, x7) =
{lg = lg; x2 = x2; x3 = x3; x5 = x5; x7 = x7 } end
let one: LogRep = LogRep(0UL, 0us, 0us, 0us, 0us)
let logshft = 50
let fac = pown 2.0 logshft
let lg10_10 = 1UL <<< logshft
let lg7_10 = (uint64 << round) <| log 7.0 / log 10.0 * fac
let lg5_10 = (uint64 << round) <| log 5.0 / log 10.0 * fac
let lg3_10 = (uint64 << round) <| log 3.0 / log 10.0 * fac
let lg2_10 = lg10_10 - lg5_10
let inline mul2 (lr: LogRep): LogRep =
LogRep(lr.lg + lg2_10, lr.x2 + 1us, lr.x3, lr.x5, lr.x7)
let inline mul3 (lr: LogRep): LogRep =
LogRep(lr.lg + lg3_10, lr.x2, lr.x3 + 1us, lr.x5, lr.x7)
let inline mul5 (lr: LogRep): LogRep =
LogRep(lr.lg + lg5_10, lr.x2, lr.x3, lr.x5 + 1us, lr.x7)
let inline mul7 (lr: LogRep): LogRep =
LogRep(lr.lg + lg7_10, lr.x2, lr.x3, lr.x5, lr.x7 + 1us)
let lr2BigInt (lr: LogRep) =
let rec xpnd n mlt rslt =
if n <= 0us then rslt
else xpnd (n - 1us) mlt (mlt * rslt)
xpnd lr.x2 2I 1I |> xpnd lr.x3 3I |> xpnd lr.x5 5I |> xpnd lr.x7 7I
type CIS<'a> = CIS of 'a * (Unit -> CIS<'a>) // infinite Co-Inductive Stream...
let cis2Seq cis =
Seq.unfold (fun (CIS(hd, tlf)) -> Some(hd, tlf())) cis
let humblesLog() =
let prmfs = [ mul7; mul5; mul3; mul2 ]
let frstpf = Seq.head prmfs
let rstpfs = Seq.tail prmfs
let frstll =
let rec nxt n = CIS(n, fun () -> nxt (frstpf n))
nxt (frstpf one)
let mkcis cis mf =
let q = Queue<LogRep>(1024)
let fv = mf one
let nv = mf fv
let rec nxt (hdv: LogRep) (CIS(chd: LogRep, ctlf) as cis) =
if hdv.lg < chd.lg then
CIS(hdv, fun () -> q.Enqueue (mf hdv); nxt (q.Dequeue()) cis)
else CIS(chd, fun () -> q.Enqueue (mf chd); nxt hdv (ctlf()))
CIS(fv, fun () -> nxt nv cis)
CIS(one, fun () -> (Seq.fold mkcis frstll rstpfs))
let comma3 v =
let s = string v
let rec loop n lst =
if n < 1 then List.fold (fun s xs ->
s + "," + xs) (List.head lst) <| List.tail lst
else let nn = max (n - 3) 0 in loop nn (s.[nn .. n - 1] :: lst)
loop (String.length s) []
let digitCountTo n ll =
let rec loop i (CIS(hd: LogRep, tlf)) cnt cacc =
if int i <= n then
if hd.lg >>> logshft < i then loop i (tlf()) (cnt + 1) cacc else
let ncacc = cacc + cnt
printfn "%4d%14s%19s" i (comma3 cnt) (comma3 ncacc)
loop (i + 1UL) (tlf()) 1 ncacc
loop 1UL ll 0 0
printfn "The first 50 humble numbers are:"
humblesLog() |> cis2Seq |> Seq.take 50 |> Seq.map lr2BigInt
|> Seq.iter (printf "%A ");printfn ""
printfn ""
let numDigits = 255
printfn "Count of humble numbers for each digit length 1-%d:" numDigits
printfn "Digits Count Accum"
let strt = System.DateTime.Now.Ticks
humblesLog() |> digitCountTo numDigits
let stop = System.DateTime.Now.Ticks
printfn "Counting took %d milliseconds" <| ((stop - strt) / 10000L)</syntaxhighlight>
{{out}}
<pre>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
Count of humble numbers for each digit length 1-255:
Digits Count Accum
1 9 9
2 36 45
3 95 140
4 197 337
5 356 693
6 579 1,272
7 882 2,154
8 1,272 3,426
9 1,767 5,193
10 2,381 7,574
11 3,113 10,687
12 3,984 14,671
13 5,002 19,673
14 6,187 25,860
15 7,545 33,405
16 9,081 42,486
17 10,815 53,301
18 12,759 66,060
19 14,927 80,987
20 17,323 98,310
21 19,960 118,270
22 22,853 141,123
23 26,015 167,138
24 29,458 196,596
25 33,188 229,784
.
.
. results as for the C++ or Pascal versions...
.
.
.
250 30,938,881 1,954,289,627
251 31,310,645 1,985,600,272
252 31,685,379 2,017,285,651
253 32,063,093 2,049,348,744
254 32,443,792 2,081,792,536
255 32,827,496 2,114,620,032
Counting took 85945 milliseconds</pre>
This, as run on an Intel i5-6500 at 3.6 GHz when running single-threaded, is about twice as fast as the Haskell version of the same due to the time lost by Haskell in lazy list operations and about twice as slow as the fastest Pascal version due to the Pascal version being completely optimized for the task of counting digits in order, which seems of little point given that ordering before counting digits as in the following code is so much easier and faster.
This takes over three hours to count the digits up to 877.
===Even Faster by Using Logarithms but Skipping Ordering Entirely===
As per the C++ Direct Generation contribution, there is no need to count the occurrences per digit length in order which saves a lot of code and execution time; as well, there is a slight optimization to do array access via pointer to save about twenty percent of the time used for array bounds checks as implemented in the following code:
<syntaxhighlight lang="fsharp">open System.Collections.Generic
open Microsoft.FSharp.NativeInterop
// a count and logarithmic approximation of the humble value...
type LogRep = struct val lg: uint64; val x2: uint16; val x3: uint16;
val x5: uint16; val x7: uint16
new(lg, x2, x3, x5, x7) =
{lg = lg; x2 = x2; x3 = x3; x5 = x5; x7 = x7 } end
let one: LogRep = LogRep(0UL, 0us, 0us, 0us, 0us)
let logshft = 50
let fac = pown 2.0 logshft
let lg10_10 = 1UL <<< logshft
let lg7_10 = (uint64 << round) <| log 7.0 / log 10.0 * fac
let lg5_10 = (uint64 << round) <| log 5.0 / log 10.0 * fac
let lg3_10 = (uint64 << round) <| log 3.0 / log 10.0 * fac
let lg2_10 = lg10_10 - lg5_10
let inline mul2 (lr: LogRep): LogRep =
LogRep(lr.lg + lg2_10, lr.x2 + 1us, lr.x3, lr.x5, lr.x7)
let inline mul3 (lr: LogRep): LogRep =
LogRep(lr.lg + lg3_10, lr.x2, lr.x3 + 1us, lr.x5, lr.x7)
let inline mul5 (lr: LogRep): LogRep =
LogRep(lr.lg + lg5_10, lr.x2, lr.x3, lr.x5 + 1us, lr.x7)
let inline mul7 (lr: LogRep): LogRep =
LogRep(lr.lg + lg7_10, lr.x2, lr.x3, lr.x5, lr.x7 + 1us)
let lr2BigInt (lr: LogRep) =
let rec xpnd n mlt rslt =
if n <= 0us then rslt
else xpnd (n - 1us) mlt (mlt * rslt)
xpnd lr.x2 2I 1I |> xpnd lr.x3 3I |> xpnd lr.x5 5I |> xpnd lr.x7 7I
type CIS<'a> = CIS of 'a * (Unit -> CIS<'a>) // infinite Co-Inductive Stream...
let cis2Seq cis =
Seq.unfold (fun (CIS(hd, tlf)) -> Some(hd, tlf())) cis
let humblesLog() =
let prmfs = [ mul7; mul5; mul3; mul2 ]
let frstpf = Seq.head prmfs
let rstpfs = Seq.tail prmfs
let frstll =
let rec nxt n = CIS(n, fun () -> nxt (frstpf n))
nxt (frstpf one)
let mkcis cis mf =
let q = Queue<LogRep>(1024)
let fv = mf one
let nv = mf fv
let rec nxt (hdv: LogRep) (CIS(chd: LogRep, ctlf) as cis) =
if hdv.lg < chd.lg then
CIS(hdv, fun () -> q.Enqueue (mf hdv); nxt (q.Dequeue()) cis)
else CIS(chd, fun () -> q.Enqueue (mf chd); nxt hdv (ctlf()))
CIS(fv, fun () -> nxt nv cis)
CIS(one, fun () -> (Seq.fold mkcis frstll rstpfs))
let comma3 v =
let s = string v
let rec loop n lst =
if n < 1 then List.fold (fun s xs ->
s + "," + xs) (List.head lst) <| List.tail lst
else let nn = max (n - 3) 0 in loop nn (s.[nn .. n - 1] :: lst)
loop (String.length s) []
printfn "The first 50 humble numbers are:"
humblesLog() |> cis2Seq |> Seq.take 50 |> Seq.map lr2BigInt
|> Seq.iter (printf "%A ");printfn ""
printfn ""
let numDigits = 877
printfn "Count of humble numbers for each digit length 1-%d:" numDigits
printfn "Digits Count Accum"
let strt = System.DateTime.Now.Ticks
let bins = Array.zeroCreate numDigits
#nowarn "9" // no warnings for the use of native pointers...
#nowarn "51"
let lmt = uint64 numDigits <<< logshft
let rec loopw w =
if w < lmt then
let rec loopx x =
if x < lmt then
let rec loopy y =
if y < lmt then
let rec loopz z =
if z < lmt then
// let ndx = z >>> logshft |> int
// bins.[ndx] <- bins.[ndx] + 1UL
// use pointers to save array bounds checking...
let ndx = &&bins.[z >>> logshft |> int]
NativePtr.write ndx (NativePtr.read ndx + 1UL)
loopz (z + lg7_10) in loopz y; loopy (y + lg5_10)
loopy x; loopx (x + lg3_10) in loopx w; loopw (w + lg2_10) in loopw 0UL
bins |> Seq.scan (fun (i, _, a) v ->
i + 1, v, a + v) (0, 0UL, 0UL) |> Seq.skip 1
|> Seq.iter (fun (i, c, a) -> printfn "%4d%14s%19s" i (comma3 c) (comma3 a))
let stop = System.DateTime.Now.Ticks
printfn "Counting took %d milliseconds" <| ((stop - strt) / 10000L)</syntaxhighlight>
{{out}}
<pre>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
Count of humble numbers for each digit length 1-877:
Digits Count Accum
1 9 9
2 36 45
3 95 140
4 197 337
5 356 693
6 579 1,272
7 882 2,154
8 1,272 3,426
9 1,767 5,193
10 2,381 7,574
11 3,113 10,687
12 3,984 14,671
13 5,002 19,673
14 6,187 25,860
15 7,545 33,405
16 9,081 42,486
17 10,815 53,301
18 12,759 66,060
19 14,927 80,987
20 17,323 98,310
21 19,960 118,270
22 22,853 141,123
23 26,015 167,138
24 29,458 196,596
25 33,188 229,784
.
.
. results as for the C++ or Pascal versions...
.
.
.
860 1,252,394,180 270,098,254,942
861 1,256,764,708 271,355,019,650
862 1,261,145,413 272,616,165,063
863 1,265,536,277 273,881,701,340
864 1,269,937,307 275,151,638,647
865 1,274,348,541 276,425,987,188
866 1,278,769,968 277,704,757,156
867 1,283,201,615 278,987,958,771
868 1,287,643,503 280,275,602,274
869 1,292,095,618 281,567,697,892
870 1,296,557,975 282,864,255,867
871 1,301,030,613 284,165,286,480
872 1,305,513,506 285,470,799,986
873 1,310,006,698 286,780,806,684
874 1,314,510,190 288,095,316,874
875 1,319,023,979 289,414,340,853
876 1,323,548,095 290,737,888,948
877 1,328,082,553 292,065,971,501
Counting took 316149 milliseconds</pre>
This is about twice as slow as the C++ or Haskell versions of the same algorithm due to being run on the DotNet JIT compiled environment.
=={{header|Factor}}==
Line 4,377 ⟶ 4,763:
17 10815
18 12759</pre>
===Faster Implementation Iterating Over Logarithms===
While the above submission is adequate for the tasts as defined, it is incredibly slow and doesn't scale linearily with increasing range as Hamming/Humble/N-smooth sequences should. The following code adapts [[Hamming_numbers#Much_faster_iterating_version_using_logarithmic_calculations|one of the Nim Hamming submissions (the fastest sequence using a queue)]], adding the extra prime factor of seven and simplifying the code, as well only using the logarithmic approximation which is adequate to the task of only showing the first 50 humble numbers and the digit counts up to a very high number of digits, as follows:
<syntaxhighlight lang="nim">import std/math, std/strutils
from std/times import inMilliseconds
from std/monotimes import getMonoTime, `-`
let lgshft = 50; let lg10 = 1'u64 shl lgshft; let fac = 2'f64.pow lgshft.float64
let lg7 = (7'f64.log10 * fac).round.uint64
let lg5 = (5'f64.log10 * fac).round.uint64
let lg3 = (3'f64.log10 * fac).round.uint64; let lg2 = lg10 - lg5
proc lr2UInt64(lr: uint64): uint64 = pow(10, (lr.float64 / fac)).round.uint64
iterator humblesLogQ(): uint64 = # {.closure.} =
var hd2 = lg2; var hd3 = lg3; var hd5 = lg5; var hd7 = lg7
var s2msk, s2hdi, s2tli, s3msk, s3hdi, s3tli, s5msk, s5hdi, s5tli = 0
var s2 = newSeq[uint64] 0
var s3 = newSeq[uint64] 0
var s5 = newSeq[uint64] 0
yield 0'u64
while true:
yield hd2
if s2tli == s2hdi:
let osz = if s2msk == 0: 512 else: s2msk + 1
s2.setLen (osz + osz); s2msk = s2.len - 1
if osz > 512:
if s2hdi == 0: s2tli = osz
else: # put extra space between tail and head...
copyMem(addr(s2[s2hdi + osz]), addr(s2[s2hdi]),
sizeof(uint64) * (osz - s2hdi)); s2hdi += osz
s2[s2tli] = hd2 + lg2; s2tli = (s2tli + 1) and s2msk
hd2 = s2[s2hdi]
if hd2 < hd3: s2hdi = (s2hdi + 1) and s2msk
else:
hd2 = hd3
if s3tli == s3hdi:
let osz = if s3msk == 0: 512 else: s3msk + 1
s3.setLen (osz + osz); s3msk = s3.len - 1
if osz > 512:
if s3hdi == 0: s3tli = osz
else: # put extra space between tail and head...
copyMem(addr(s3[s3hdi + osz]), addr(s3[s3hdi]),
sizeof(uint64) * (osz - s3hdi)); s3hdi += osz
s3[s3tli] = hd3 + lg3; s3tli = (s3tli + 1) and s3msk
hd3 = s3[s3hdi]
if hd3 < hd5: s3hdi = (s3hdi + 1) and s3msk
else:
hd3 = hd5
if s5tli == s5hdi:
let osz = if s5msk == 0: 512 else: s5msk + 1
s5.setLen (osz + osz); s5msk = s5.len - 1
if osz > 512:
if s5hdi == 0: s5tli = osz
else: # put extra space between tail and head...
copyMem(addr(s5[s5hdi + osz]), addr(s5[s5hdi]),
sizeof(uint64) * (osz - s5hdi)); s5hdi += osz
s5[s5tli] = hd5 + lg5; s5tli = (s5tli + 1) and s5msk
hd5 = s5[s5hdi]
if hd5 < hd7: s5hdi = (s5hdi + 1) and s5msk
else: hd5 = hd7; hd7 += lg7
proc commaString(s: string): string =
let sz = s.len; let sqlen = (sz + 2) div 3
var sq = newSeq[string](sqlen); var ndx = sqlen - 1
for i in countdown(sz - 1, 0, 3): sq[ndx] = s[(max(i-2, 0) .. i)]; ndx -= 1
sq.join ","
# testing it...
let numdigits = 255.uint64
echo "First 50 Humble numbers:"
var cnt = 0
for h in humblesLogQ():
stdout.write $h.lr2UInt64, " "; cnt += 1
if cnt >= 50: break
echo "\r\nCount of humble numbers for each digit length 1-", $numdigits, ":"
echo "Digits Count Accum"
let lmt = lg10 * numdigits
let strt = getMonoTime()
var cdigits = 0'u64; cnt = 0; var acnt = 0.int
for h in humblesLogQ():
if (h shr lgshft) <= cdigits: cnt += 1
else:
cdigits += 1; acnt += cnt
echo ($cdigits).align(4) & ($cnt).commaString.align(14) &
($acnt).commaString.align(19)
cnt = 1
if cdigits >= numdigits: break
let elpsd = (getMonoTime() - strt).inMilliseconds
echo "Counting took ", elpsd, " milliseconds."</syntaxhighlight>
{{out}}
<pre>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
Count of humble numbers for each digit length 1-255:
Digits Count Accum
1 9 9
2 36 45
3 95 140
4 197 337
5 356 693
6 579 1,272
7 882 2,154
8 1,272 3,426
9 1,767 5,193
10 2,381 7,574
11 3,113 10,687
12 3,984 14,671
13 5,002 19,673
14 6,187 25,860
15 7,545 33,405
16 9,081 42,486
17 10,815 53,301
18 12,759 66,060
19 14,927 80,987
20 17,323 98,310
21 19,960 118,270
22 22,853 141,123
23 26,015 167,138
24 29,458 196,596
25 33,188 229,784
.
.
. results as for the C++ or Pascal versions...
.
.
.
250 30,938,881 1,954,289,627
251 31,310,645 1,985,600,272
252 31,685,379 2,017,285,651
253 32,063,093 2,049,348,744
254 32,443,792 2,081,792,536
255 32,827,496 2,114,620,032
Counting took 6096 milliseconds.</pre>
The above code as run on an Intel i5-6500 at 3.6 GHz (boost single-threaded) is faster than the Pascal version doing about the same as to algorithm, and would be able to show all the digit counts up to 877 digits in about 15 minutes (about six times faster than the Pascal version) except that this machine doesn't have enough memory (about eight Gigabytes required plus as required by the operating system and run-time, and this machine only has eight Gigabytes total), showing that this code is many times faster than the Pascal version while simpler to read.
===Direct Calculation Without Sorting the Sequence===
As noticed in the C++ Direct Generation - Variant submission, there is no need for the complexity and execution time cost of processing the humble numbers in order in order to show the digit counts; the following Nim code implements that algorithm, with the first fifty humble numbers able to be produced by any simple sequence generator, here using the generator from the submission above this:
<syntaxhighlight lang="nim">import std/math, std/strutils
from std/times import inMilliseconds
from std/monotimes import getMonoTime, `-`
let lgshft = 50; let lg10 = 1'u64 shl lgshft; let fac = 2'f64.pow lgshft.float64
let lg7 = (7'f64.log10 * fac).round.uint64
let lg5 = (5'f64.log10 * fac).round.uint64
let lg3 = (3'f64.log10 * fac).round.uint64; let lg2 = lg10 - lg5
proc lr2UInt64(lr: uint64): uint64 = pow(10, (lr.float64 / fac)).round.uint64
iterator humblesLogQ(): uint64 = # {.closure.} =
var hd2 = lg2; var hd3 = lg3; var hd5 = lg5; var hd7 = lg7
var s2msk, s2hdi, s2tli, s3msk, s3hdi, s3tli, s5msk, s5hdi, s5tli = 0
var s2 = newSeq[uint64] 0
var s3 = newSeq[uint64] 0
var s5 = newSeq[uint64] 0
yield 0'u64
while true:
yield hd2
if s2tli == s2hdi:
let osz = if s2msk == 0: 512 else: s2msk + 1
s2.setLen (osz + osz); s2msk = s2.len - 1
if osz > 512:
if s2hdi == 0: s2tli = osz
else: # put extra space between tail and head...
copyMem(addr(s2[s2hdi + osz]), addr(s2[s2hdi]),
sizeof(uint64) * (osz - s2hdi)); s2hdi += osz
s2[s2tli] = hd2 + lg2; s2tli = (s2tli + 1) and s2msk
hd2 = s2[s2hdi]
if hd2 < hd3: s2hdi = (s2hdi + 1) and s2msk
else:
hd2 = hd3
if s3tli == s3hdi:
let osz = if s3msk == 0: 512 else: s3msk + 1
s3.setLen (osz + osz); s3msk = s3.len - 1
if osz > 512:
if s3hdi == 0: s3tli = osz
else: # put extra space between tail and head...
copyMem(addr(s3[s3hdi + osz]), addr(s3[s3hdi]),
sizeof(uint64) * (osz - s3hdi)); s3hdi += osz
s3[s3tli] = hd3 + lg3; s3tli = (s3tli + 1) and s3msk
hd3 = s3[s3hdi]
if hd3 < hd5: s3hdi = (s3hdi + 1) and s3msk
else:
hd3 = hd5
if s5tli == s5hdi:
let osz = if s5msk == 0: 512 else: s5msk + 1
s5.setLen (osz + osz); s5msk = s5.len - 1
if osz > 512:
if s5hdi == 0: s5tli = osz
else: # put extra space between tail and head...
copyMem(addr(s5[s5hdi + osz]), addr(s5[s5hdi]),
sizeof(uint64) * (osz - s5hdi)); s5hdi += osz
s5[s5tli] = hd5 + lg5; s5tli = (s5tli + 1) and s5msk
hd5 = s5[s5hdi]
if hd5 < hd7: s5hdi = (s5hdi + 1) and s5msk
else: hd5 = hd7; hd7 += lg7
proc commaString(s: string): string =
let sz = s.len; let sqlen = (sz + 2) div 3
var sq = newSeq[string](sqlen); var ndx = sqlen - 1
for i in countdown(sz - 1, 0, 3): sq[ndx] = s[(max(i-2, 0) .. i)]; ndx -= 1
sq.join ","
# testing it...
let numdigits = 877.uint64
echo "First 50 Humble numbers:"
var cnt = 0
for h in humblesLogQ():
stdout.write $h.lr2UInt64, " "; cnt += 1
if cnt >= 50: break
echo "\r\nCount of humble numbers for each digit length 1-", $numdigits, ":"
echo "Digits Count Accum"
let lmt = lg10 * numdigits
let strt = getMonoTime()
var bins = newSeq[int](numdigits)
for w in countup(0'u64, lmt, lg7):
for x in countup(w, lmt, lg5):
for y in countup(x, lmt, lg3):
for z in countup(y, lmt, lg2):
bins[z shr lgshft] += 1
var a = 0
for i, c in bins:
a += c
echo ($(i + 1)).align(4) & ($c).commaString.align(14) &
($a).commaString.align(19)
let elpsd = (getMonoTime() - strt).inMilliseconds
echo "Counting took ", elpsd, " milliseconds."</syntaxhighlight>
{{out}}
<pre>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
Count of humble numbers for each digit length 1-877:
Digits Count Accum
1 9 9
2 36 45
3 95 140
4 197 337
5 356 693
6 579 1,272
7 882 2,154
8 1,272 3,426
9 1,767 5,193
10 2,381 7,574
11 3,113 10,687
12 3,984 14,671
13 5,002 19,673
14 6,187 25,860
15 7,545 33,405
16 9,081 42,486
17 10,815 53,301
18 12,759 66,060
19 14,927 80,987
20 17,323 98,310
21 19,960 118,270
22 22,853 141,123
23 26,015 167,138
24 29,458 196,596
25 33,188 229,784
.
.
. results as for the C++ or Pascal versions...
.
.
.
860 1,252,394,180 270,098,254,942
861 1,256,764,708 271,355,019,650
862 1,261,145,413 272,616,165,063
863 1,265,536,277 273,881,701,340
864 1,269,937,307 275,151,638,647
865 1,274,348,541 276,425,987,188
866 1,278,769,968 277,704,757,156
867 1,283,201,615 278,987,958,771
868 1,287,643,503 280,275,602,274
869 1,292,095,618 281,567,697,892
870 1,296,557,975 282,864,255,867
871 1,301,030,613 284,165,286,480
872 1,305,513,506 285,470,799,986
873 1,310,006,698 286,780,806,684
874 1,314,510,190 288,095,316,874
875 1,319,023,979 289,414,340,853
876 1,323,548,095 290,737,888,948
877 1,328,082,553 292,065,971,501
Counting took 171076 milliseconds.</pre>
The above time as run on an Intel i5-6500 at 3.6 GHz with single-threaded boost is about the same speed as any of the fast language implementations of the same algorithm, including Haskell.
=={{header|Pascal}}==
Line 5,782 ⟶ 6,458:
The 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
</pre>
=={{header|RPL}}==
Brute force is summoned to generate the list of the first humble numbers, but direct humble numbers generation and immediate digit counting allow to obtain the distribution of humble numbers below a user-defined value in a few seconds with an emulator, requiring a few stack levels and a vector sized at the maximum number of digits only.
On a 4-bit calculator with 32 Mb RAM, it takes 25 seconds to get the first 50 numbers and 9 minutes to count all the humble numbers under 1,000,000
{{works with|HP|48}}
≪ '''CASE'''
DUP 1 == '''THEN END'''
DUP 2 MOD NOT '''THEN''' 2 / <span style="color:blue>H?</span> '''END'''
DUP 3 MOD NOT '''THEN''' 3 / <span style="color:blue>H?</span> '''END'''
DUP 5 MOD NOT '''THEN''' 5 / <span style="color:blue>H?</span> '''END'''
DUP 7 MOD NOT '''THEN''' 7 / <span style="color:blue>H?</span> '''END'''
NOT '''END'''
≫ '<span style="color:blue>H?</span>' STO
≪ { } 0 → j
≪ '''WHILE''' DUP2 SIZE > '''REPEAT'''
'j' INCR
'''IF''' <span style="color:blue>H?</span> '''THEN''' j + '''END'''
'''END''' SWAP DROP
≫ ≫ '<span style="color:blue>HLIST</span>' STO
{{works with|HP|28}}
≪ 1 4 '''FOR''' j
DUP LN { 2 3 5 7 } j GET LN / CEIL SWAP '''NEXT''' <span style="color:grey>@ max exponent for n factor is ceil(log(max value)/log(n))</span>
DUP LOG CEIL { } + 0 CON <span style="color:grey>@ create vector of counters</span>
→ m2 m3 m5 m7 max cnt
≪ 1
0 m2 '''FOR''' j
j 2 1 IFTE * DUP
0 m3 '''FOR''' k
k 3 1 IFTE * DUP
0 m5 '''FOR''' m
m 5 1 IFTE * DUP
0 m7 '''FOR''' n
n 7 1 IFTE *
'''IF''' DUP max ≤ '''THEN'''
cnt OVER XPON 1 + DUP2 GET 1 + PUT 'cnt' STO
'''ELSE''' m7 'n' STO '''END''' <span style="color:grey>@ only way to break a FOR..NEXT loop in RPL</span>
'''NEXT''' DROP
'''NEXT''' DROP
'''NEXT''' DROP
'''NEXT''' DROP
cnt
≫ ≫ '<span style="color:blue>HCNT</span>' STO
50 <span style="color:blue>HLIST</span>
999999999999 <span style="color:blue>HCNT</span>
{{out}}
<pre>
2: { 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 }
1: [ 9 36 95 197 356 579 882 1272 1767 2381 3113 3984 ]
</pre>
Line 6,103 ⟶ 6,832:
{{libheader|Wren-math}}
{{libheader|Wren-sort}}
To avoid resorting to Wren-long or Wren-big, we limit this to 16 digit integers which is the maximum Wren can handle 'natively'.
<syntaxhighlight lang="
import "./math" for
import "./sort" for Find
var humble = Fn.new { |n|
Line 6,146 ⟶ 6,875:
System.print(h[0..49])
var f = Find.all(h,
var maxUsed = f[0] ? f[2].min + 1 : f[2].min
var maxDigits = 16 //
var counts = List.filled(maxDigits + 1, 0)
var digits = 1
| |||