Humble numbers
You are encouraged to solve this task according to the task description, using any language you may know.
Humble numbers are positive integers which have no prime factors > 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
11l
<lang 11l>F is_humble(i)
I i <= 1 R 1B I i % 2 == 0 {R is_humble(i I/ 2)} I i % 3 == 0 {R is_humble(i I/ 3)} I i % 5 == 0 {R is_humble(i I/ 5)} I i % 7 == 0 {R is_humble(i I/ 7)} R 0B
DefaultDict[Int, Int] humble V limit = 7F'FF V count = 0 V num = 1
L count < limit
I is_humble(num) humble[String(num).len]++ I count < 50 print(num, end' ‘ ’) count++ num++
print() print() print(‘Of the first ’count‘ humble numbers:’)
L(num) 1 .< humble.len - 1
I num !C humble L.break print(‘#5 have #. digits’.format(humble[num], num))</lang>
- Output:
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 32767 humble numbers: 9 have 1 digits 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 1767 have 9 digits
Ada
<lang Ada>with Ada.Text_IO;
procedure Show_Humble is
type Positive is range 1 .. 2**63 - 1; First : constant Positive := Positive'First; Last : constant Positive := 999_999_999;
function Is_Humble (I : in Positive) return Boolean is begin if I <= 1 then return True; elsif I mod 2 = 0 then return Is_Humble (I / 2); elsif I mod 3 = 0 then return Is_Humble (I / 3); elsif I mod 5 = 0 then return Is_Humble (I / 5); elsif I mod 7 = 0 then return Is_Humble (I / 7); else return False; end if; end Is_Humble;
subtype Digit_Range is Natural range First'Image'Length - 1 .. Last'Image'Length - 1; Digit_Count : array (Digit_Range) of Natural := (others => 0);
procedure Count_Humble_Digits is use Ada.Text_IO; Humble_Count : Natural := 0; Len : Natural; begin Put_Line ("The first 50 humble numbers:"); for N in First .. Last loop if Is_Humble (N) then Len := N'Image'Length - 1; Digit_Count (Len) := Digit_Count (Len) + 1;
if Humble_Count < 50 then Put (N'Image); Put (" "); end if; Humble_Count := Humble_Count + 1; end if; end loop; New_Line (2); end Count_Humble_Digits;
procedure Show_Digit_Counts is package Natural_IO is new Ada.Text_IO.Integer_IO (Natural); use Ada.Text_IO; use Natural_IO;
Placeholder : String := "Digits Count"; Image_Digit : String renames Placeholder (1 .. 6); Image_Count : String renames Placeholder (8 .. Placeholder'Last); begin Put_Line ("The digit counts of humble numbers:"); Put_Line (Placeholder); for Digit in Digit_Count'Range loop Put (Image_Digit, Digit); Put (Image_Count, Digit_Count (Digit)); Put_Line (Placeholder); end loop; end Show_Digit_Counts;
begin
Count_Humble_Digits; Show_Digit_Counts;
end Show_Humble;</lang>
- Output:
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 The digit counts of humble numbers: Digits Count 1 9 2 36 3 95 4 197 5 356 6 579 7 882 8 1272 9 1767
ALGOL W
As noted by other samples, this is similar to the Hamming Numbers task. This is a modified version of the Algol W solution for Hamming Numbers. The numbers are generated in sequence. <lang algolw>begin % find some Humble numbers - numbers with no prime factors above 7 %
% returns the minimum of a and b % integer procedure min ( integer value a, b ) ; if a < b then a else b; % find and print Humble Numbers % integer MAX_HUMBLE; MAX_HUMBLE := 2048; begin integer array H( 1 :: MAX_HUMBLE ); integer p2, p3, p5, p7, last2, last3, last5, last7, h1, h2, h3, h4, h5, h6; i_w := 1; s_w := 1; % output formatting % % 1 is the first Humble number % H( 1 ) := 1; h1 := h2 := h3 := h4 := h5 := h6 := 0; last2 := last3 := last5 := last7 := 1; p2 := 2; p3 := 3; p5 := 5; p7 := 7; for hPos := 2 until MAX_HUMBLE do begin integer m; % the next Humble number is the lowest of the next multiple of 2, 3, 5, 7 % m := min( min( min( p2, p3 ), p5 ), p7 ); H( hPos ) := m; if m = p2 then begin % the Humble number was the next multiple of 2 % % the next multiple of 2 will now be twice the Humble number following % % the previous multple of 2 % last2 := last2 + 1; p2 := 2 * H( last2 ) end if_used_power_of_2 ; if m = p3 then begin last3 := last3 + 1; p3 := 3 * H( last3 ) end if_used_power_of_3 ; if m = p5 then begin last5 := last5 + 1; p5 := 5 * H( last5 ) end if_used_power_of_5 ; if m = p7 then begin last7 := last7 + 1; p7 := 7 * H( last7 ) end if_used_power_of_5 ; end for_hPos ; i_w := 1; s_w := 1; % output formatting % write( H( 1 ) ); for hPos := 2 until 50 do writeon( H( hPos ) ); for hPos := 1 until MAX_HUMBLE do begin integer m; m := H( hPos ); if m < 10 then h1 := h1 + 1 else if m < 100 then h2 := h2 + 1 else if m < 1000 then h3 := h3 + 1 else if m < 10000 then h4 := h4 + 1 else if m < 100000 then h5 := h5 + 1 else if m < 1000000 then h6 := h6 + 1 end for_hPos ; i_w := 5; s_w := 0; write( "there are", h1, " Humble numbers with 1 digit" ); write( "there are", h2, " Humble numbers with 2 digits" ); write( "there are", h3, " Humble numbers with 3 digits" ); write( "there are", h4, " Humble numbers with 4 digits" ); write( "there are", h5, " Humble numbers with 5 digits" ); write( "there are", h6, " Humble numbers with 6 digits" ) end
end.</lang>
- Output:
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 there are 9 Humble numbers with 1 digit there are 36 Humble numbers with 2 digits there are 95 Humble numbers with 3 digits there are 197 Humble numbers with 4 digits there are 356 Humble numbers with 5 digits there are 579 Humble numbers with 6 digits
AWK
<lang AWK>
- syntax: GAWK -f HUMBLE_NUMBERS.AWK
- sorting:
- PROCINFO["sorted_in"] is used by GAWK
- SORTTYPE is used by Thompson Automation's TAWK
BEGIN {
PROCINFO["sorted_in"] = "@ind_num_asc" ; SORTTYPE = 1 n = 1 for (; count<5193; n++) { if (is_humble(n)) { arr[length(n)]++ if (count++ < 50) { printf("%d ",n) } } } printf("\nCount Digits of the first %d humble numbers:\n",count) for (i in arr) { printf("%5d %6d\n",arr[i],i) } exit(0)
} function is_humble(i) {
if (i <= 1) { return(1) } if (i % 2 == 0) { return(is_humble(i/2)) } if (i % 3 == 0) { return(is_humble(i/3)) } if (i % 5 == 0) { return(is_humble(i/5)) } if (i % 7 == 0) { return(is_humble(i/7)) } return(0)
} </lang>
- Output:
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 Digits of the first 5193 humble numbers: 9 1 36 2 95 3 197 4 356 5 579 6 882 7 1272 8 1767 9
C
<lang C>#include <limits.h>
- include <stdbool.h>
- include <stdio.h>
- include <string.h>
bool isHumble(int i) {
if (i <= 1) return true; if (i % 2 == 0) return isHumble(i / 2); if (i % 3 == 0) return isHumble(i / 3); if (i % 5 == 0) return isHumble(i / 5); if (i % 7 == 0) return isHumble(i / 7); return false;
}
int main() {
int limit = SHRT_MAX; int humble[16]; int count = 0; int num = 1; char buffer[16];
memset(humble, 0, sizeof(humble));
for (; count < limit; num++) { if (isHumble(num)) { size_t len; sprintf_s(buffer, sizeof(buffer), "%d", num); len = strlen(buffer); if (len >= 16) { break; } humble[len]++;
if (count < 50) { printf("%d ", num); } count++; } } printf("\n\n");
printf("Of the first %d humble numbers:\n", count); for (num = 1; num < 10; num++) { printf("%5d have %d digits\n", humble[num], num); }
return 0;
}</lang>
- Output:
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 32767 humble numbers: 9 have 1 digits 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 1767 have 9 digits
C#
<lang csharp>using System; using System.Collections.Generic;
namespace HumbleNumbers {
class Program { static bool IsHumble(int i) { if (i <= 1) return true; if (i % 2 == 0) return IsHumble(i / 2); if (i % 3 == 0) return IsHumble(i / 3); if (i % 5 == 0) return IsHumble(i / 5); if (i % 7 == 0) return IsHumble(i / 7); return false; }
static void Main() { var limit = short.MaxValue; Dictionary<int, int> humble = new Dictionary<int, int>(); var count = 0; var num = 1;
while (count < limit) { if (IsHumble(num)) { var str = num.ToString(); var len = str.Length; if (humble.ContainsKey(len)) { humble[len]++; } else { humble[len] = 1; } if (count < 50) Console.Write("{0} ", num); count++; } num++; } Console.WriteLine("\n");
Console.WriteLine("Of the first {0} humble numbers:", count); num = 1; while (num < humble.Count - 1) { if (humble.ContainsKey(num)) { var c = humble[num]; Console.WriteLine("{0,5} have {1,2} digits", c, num); num++; } else { break; } } } }
}</lang>
- Output:
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 32767 humble numbers: 9 have 1 digits 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 1767 have 9 digits
Direct Generation
<lang csharp>#define BI
using System; using System.Linq; using System.Collections.Generic;
- if BI
using UI = System.Numerics.BigInteger;
- else
using UI = System.UInt64;
- endif
class Program {
static void Main(string[] args) {
- if BI
const int max = 100;
- else
const int max = 19;
- endif
List<UI> h = new List<UI> { 1 }; UI x2 = 2, x3 = 3, x5 = 5, x7 = 7, hm = 2, lim = 10; int i = 0, j = 0, k = 0, l = 0, lc = 0, d = 1; Console.WriteLine("Digits Count Time Mb used"); var elpsd = -DateTime.Now.Ticks; do { h.Add(hm); if (hm == x2) x2 = h[++i] << 1; if (hm == x3) x3 = (h[++j] << 1) + h[j]; if (hm == x5) x5 = (h[++k] << 2) + h[k]; if (hm == x7) x7 = (h[++l] << 3) - h[l]; hm = x2; if (x3 < hm) hm = x3; if (x5 < hm) hm = x5; if (x7 < hm) hm = x7; if (hm >= lim) { Console.WriteLine("{0,3} {1,9:n0} {2,9:n0} ms {3,9:n0}", d, h.Count - lc, (elpsd + DateTime.Now.Ticks) / 10000, GC.GetTotalMemory(false) / 1000000); lc = h.Count; if (++d > max) break; lim *= 10; } } while (true); Console.WriteLine("{0,13:n0} Total", lc); int firstAmt = 50; Console.WriteLine("The first {0} humble numbers are: {1}", firstAmt, string.Join(" ",h.Take(firstAmt))); }
}</lang>
- Output:
Results from a core i7-7700 @ 3.6Ghz.
BigIntegers: (tabulates up to 100 digits in about 3/4 of a minute, but a lot of memory is consumed - 4.2 GB)
Digits Count Time Mb used 1 9 5 ms 0 2 36 7 ms 0 3 95 7 ms 0 4 197 7 ms 0 5 356 7 ms 0 6 579 8 ms 0 7 882 8 ms 0 8 1,272 9 ms 0 9 1,767 10 ms 1 10 2,381 11 ms 2 11 3,113 14 ms 3 12 3,984 23 ms 1 13 5,002 27 ms 4 14 6,187 34 ms 2 15 7,545 39 ms 6 16 9,081 60 ms 4 17 10,815 75 ms 3 18 12,759 88 ms 11 19 14,927 105 ms 4 20 17,323 116 ms 7 21 19,960 157 ms 6 22 22,853 183 ms 16 23 26,015 217 ms 10 24 29,458 241 ms 14 25 33,188 279 ms 14 26 37,222 327 ms 24 27 41,568 365 ms 28 28 46,245 408 ms 30 29 51,254 472 ms 23 30 56,618 526 ms 26 31 62,338 607 ms 49 32 68,437 697 ms 39 33 74,917 762 ms 47 34 81,793 819 ms 48 35 89,083 894 ms 53 36 96,786 1,017 ms 56 37 104,926 1,114 ms 58 38 113,511 1,245 ms 99 39 122,546 1,350 ms 104 40 132,054 1,473 ms 107 41 142,038 1,640 ms 101 42 152,515 1,772 ms 106 43 163,497 1,902 ms 113 44 174,986 2,040 ms 121 45 187,004 2,240 ms 165 46 199,565 2,371 ms 178 47 212,675 2,501 ms 187 48 226,346 2,640 ms 194 49 240,590 2,792 ms 209 50 255,415 2,977 ms 223 51 270,843 3,246 ms 236 52 286,880 3,463 ms 248 53 303,533 3,745 ms 395 54 320,821 3,988 ms 414 55 338,750 4,203 ms 428 56 357,343 4,447 ms 443 57 376,599 4,734 ms 460 58 396,533 5,127 ms 418 59 417,160 5,442 ms 438 60 438,492 5,782 ms 464 61 460,533 6,139 ms 489 62 483,307 6,519 ms 514 63 506,820 6,918 ms 545 64 531,076 7,560 ms 706 65 556,104 7,986 ms 740 66 581,902 8,591 ms 771 67 608,483 9,056 ms 805 68 635,864 9,470 ms 843 69 664,053 9,988 ms 876 70 693,065 10,597 ms 918 71 722,911 11,102 ms 961 72 753,593 11,880 ms 1,000 73 785,141 12,471 ms 1,047 74 817,554 13,056 ms 1,092 75 850,847 13,767 ms 1,140 76 885,037 14,551 ms 1,724 77 920,120 15,362 ms 1,776 78 956,120 16,131 ms 1,834 79 993,058 16,986 ms 1,901 80 1,030,928 17,776 ms 1,967 81 1,069,748 18,658 ms 2,037 82 1,109,528 19,866 ms 1,839 83 1,150,287 20,780 ms 1,911 84 1,192,035 21,748 ms 1,985 85 1,234,774 22,715 ms 2,067 86 1,278,527 23,799 ms 2,147 87 1,323,301 24,826 ms 2,235 88 1,369,106 25,953 ms 2,322 89 1,415,956 27,119 ms 2,411 90 1,463,862 29,195 ms 3,041 91 1,512,840 30,487 ms 3,138 92 1,562,897 31,732 ms 3,241 93 1,614,050 32,995 ms 3,339 94 1,666,302 34,338 ms 3,451 95 1,719,669 35,809 ms 3,560 96 1,774,166 37,386 ms 3,673 97 1,829,805 38,912 ms 3,800 98 1,886,590 40,474 ms 3,933 99 1,944,540 42,073 ms 4,077 100 2,003,661 43,808 ms 4,222 51,428,827 Total 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
UInt64s: (comment out "#define BI" at the top of the code)
Digits Count Time Mb used 1 9 4 ms 0 2 36 5 ms 0 3 95 6 ms 0 4 197 6 ms 0 5 356 6 ms 0 6 579 6 ms 0 7 882 6 ms 0 8 1,272 6 ms 0 9 1,767 6 ms 0 10 2,381 6 ms 0 11 3,113 6 ms 0 12 3,984 6 ms 0 13 5,002 6 ms 0 14 6,187 6 ms 0 15 7,545 7 ms 1 16 9,081 7 ms 1 17 10,815 7 ms 1 18 12,759 7 ms 2 19 14,927 7 ms 2 80,987 Total 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
Direct Generation via Logarithms
Similar to one of the design elements of the Pascal entry (and a few others), add logarithms together instead of multiplying big numbers. Surprisingly, only about 10-11 digits of precision is needed, so the fixed-point logs fit in an UInt64. It's a very bad memory hog though (17GB!), so the Pascal entry is much better in that respect. It's quick, doing 255 digits in 17 seconds (about 60x faster than the Direct Generation BigInteger version above), comparable to the speed of the Pascal vesion. It does double duty (range 1..nth and digits tabulation), which slows performance a little. When the code that generates the range (1..nth) is removed, it can execute in about 15 seconds. (on the core i7-7700 @ 3.6Ghz)
It does have an issue with reporting humble numbers greater than ~1e19, as the code that returns the fixed-point log cannot fit the result into a UInt64. This is a non-issue for this task because the largest humble number asked for is 120. (Heh, on the Hamming Number task, that would be an issue.) However, the count of humble numbers in each decade is correct. If it is necessary to report large humble numbers, the System.Numerics library could be used and a function written to provide an arbitrary precision BigInteger.Exp() result.
Why use fixed-point logarithms of UIint64 instead of double? Because the rounding of the doubles when added together throws the sums off a bit so they don't match properly when incrementing the i, j, k, & l variables. If one were to change the 'fac" variable to a larger number, such as 1e15, there is too much "noise" on the least significant bits and the ijkl variables advance unevenly enough to throw off some of the counts. Some of the solutions presented here implement an "error banding" check to defeat this issue, but it seems a bit over complicated.
<lang csharp>using System; using UI = System.UInt64;
class Program {
// write a range (1..num) to the console when num < 0, just write the nth when num > 0, otherwise write the digits tabulation // note: when doing range or nth, if num > ~1e19 the results will appear incorrect as UInt64 can't express numbers that large static void humLog(int digs, int num = 0) { bool range = num < 0, nth = num > 0, small = range | nth; num = Math.Abs(num); int maxdim = num; if (range | nth) digs = num.ToString().Length; // calculate number of digits when range or nth is specified //const int maxdim = 2_147_483_647; // 2GB limit (Int32.MaxValue), causes out of memory error //const int maxdim = 2_146_435_071; // max practical amount //const int maxdim = 2_114_620_032; // amount needed for 255 digits else maxdim = 2_114_620_032; const double fac = 1e11; UI lb2 = (UI)Math.Round(fac * Math.Log(2)), lb3 = (UI)Math.Round(fac * Math.Log(3)), lb5 = (UI)Math.Round(fac * Math.Log(5)), lb7 = (UI)Math.Round(fac * Math.Log(7)), lb0 = (UI)Math.Round(fac * Math.Log(10)), hm, x2 = lb2, x3 = lb3, x5 = lb5, x7 = lb7, lim = lb0; int i = 0, j = 0, k = 0, l = 0, lc = 0, d = 1, hi = 1; UI[] h = new UI[maxdim]; h[0] = 1; var st = DateTime.Now.Ticks; if (range) Console.Write("The first {0} humble numbers are: 1 ", num); else if (nth) Console.Write("The {0}{1} humble number is ", num, (num % 10) switch { 1 => "st", 2 => "nd", 3 => "rd", _ => "th", }); else Console.WriteLine("\nDigits Dig Count Tot Count Time Mb used"); do { hm = x2; if (x3 < hm) hm = x3; if (x5 < hm) hm = x5; if (x7 < hm) hm = x7; // select the minimum if (hm >= lim && !small) { // passed another decade, so output results Console.WriteLine("{0,3} {1,13:n0} {4,16:n0} {2,9:n3}s {3,9:n0}", d, hi - lc, ((DateTime.Now.Ticks - st) / 10000)/1000.0, GC.GetTotalMemory(false) / 1000000, hi); lc = hi; if (++d > digs) break; lim += lb0; } h[hi++] = (hm); if (small) { if (nth && hi == num) { Console.WriteLine(Math.Round(Math.Exp(hm / fac))); break; } if (range) { Console.Write("{0} ", Math.Round(Math.Exp(hm / fac))); if (hi == num) { Console.WriteLine(); break; } } } if (hm == x2) x2 = h[++i] + lb2; if (hm == x3) x3 = h[++j] + lb3; if (hm == x5) x5 = h[++k] + lb5; if (hm == x7) x7 = h[++l] + lb7; } while (true); if (!(range | nth)) Console.WriteLine("{0,17:n0} Total", lc); } static void Main(string[] args) { humLog(0, -50); // see the range 1..50 humLog(255); // see tabulation for digits 1 to 255 }
}</lang>
- Output:
verified results against the Pascal entry:
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 Digits Dig Count Tot Count Time Mb used 1 9 9 0.000s 16,917 2 36 45 0.038s 16,917 3 95 140 0.039s 16,917 4 197 337 0.039s 16,917 5 356 693 0.039s 16,917 6 579 1,272 0.039s 16,917 7 882 2,154 0.039s 16,917 8 1,272 3,426 0.039s 16,917 9 1,767 5,193 0.040s 16,917 10 2,381 7,574 0.040s 16,917 11 3,113 10,687 0.040s 16,917 12 3,984 14,671 0.040s 16,917 13 5,002 19,673 0.040s 16,917 14 6,187 25,860 0.041s 16,917 15 7,545 33,405 0.041s 16,917 16 9,081 42,486 0.041s 16,917 17 10,815 53,301 0.041s 16,917 18 12,759 66,060 0.041s 16,917 19 14,927 80,987 0.042s 16,917 20 17,323 98,310 0.042s 16,917 21 19,960 118,270 0.043s 16,917 22 22,853 141,123 0.044s 16,917 23 26,015 167,138 0.045s 16,917 24 29,458 196,596 0.045s 16,917 25 33,188 229,784 0.047s 16,917 26 37,222 267,006 0.047s 16,917 27 41,568 308,574 0.048s 16,917 28 46,245 354,819 0.049s 16,917 29 51,254 406,073 0.050s 16,917 30 56,618 462,691 0.051s 16,917 31 62,338 525,029 0.052s 16,917 32 68,437 593,466 0.088s 16,917 33 74,917 668,383 0.094s 16,917 34 81,793 750,176 0.095s 16,917 35 89,083 839,259 0.096s 16,917 36 96,786 936,045 0.097s 16,917 37 104,926 1,040,971 0.098s 16,917 38 113,511 1,154,482 0.099s 16,917 39 122,546 1,277,028 0.100s 16,917 40 132,054 1,409,082 0.101s 16,917 41 142,038 1,551,120 0.102s 16,917 42 152,515 1,703,635 0.104s 16,917 43 163,497 1,867,132 0.106s 16,917 44 174,986 2,042,118 0.109s 16,917 45 187,004 2,229,122 0.111s 16,917 46 199,565 2,428,687 0.113s 16,917 47 212,675 2,641,362 0.116s 16,917 48 226,346 2,867,708 0.118s 16,917 49 240,590 3,108,298 0.120s 16,917 50 255,415 3,363,713 0.123s 16,917 51 270,843 3,634,556 0.145s 16,917 52 286,880 3,921,436 0.169s 16,917 53 303,533 4,224,969 0.172s 16,917 54 320,821 4,545,790 0.176s 16,917 55 338,750 4,884,540 0.181s 16,917 56 357,343 5,241,883 0.225s 16,917 57 376,599 5,618,482 0.229s 16,917 58 396,533 6,015,015 0.233s 16,917 59 417,160 6,432,175 0.238s 16,917 60 438,492 6,870,667 0.275s 16,917 61 460,533 7,331,200 0.279s 16,917 62 483,307 7,814,507 0.285s 16,917 63 506,820 8,321,327 0.290s 16,917 64 531,076 8,852,403 0.299s 16,917 65 556,104 9,408,507 0.319s 16,917 66 581,902 9,990,409 0.341s 16,917 67 608,483 10,598,892 0.348s 16,917 68 635,864 11,234,756 0.370s 16,917 69 664,053 11,898,809 0.393s 16,917 70 693,065 12,591,874 0.413s 16,917 71 722,911 13,314,785 0.436s 16,917 72 753,593 14,068,378 0.457s 16,917 73 785,141 14,853,519 0.480s 16,917 74 817,554 15,671,073 0.488s 16,917 75 850,847 16,521,920 0.497s 16,917 76 885,037 17,406,957 0.506s 16,917 77 920,120 18,327,077 0.514s 16,917 78 956,120 19,283,197 0.522s 16,917 79 993,058 20,276,255 0.531s 16,917 80 1,030,928 21,307,183 0.540s 16,917 81 1,069,748 22,376,931 0.548s 16,917 82 1,109,528 23,486,459 0.559s 16,917 83 1,150,287 24,636,746 0.570s 16,917 84 1,192,035 25,828,781 0.580s 16,917 85 1,234,774 27,063,555 0.597s 16,917 86 1,278,527 28,342,082 0.608s 16,917 87 1,323,301 29,665,383 0.622s 16,917 88 1,369,106 31,034,489 0.637s 16,917 89 1,415,956 32,450,445 0.652s 16,917 90 1,463,862 33,914,307 0.665s 16,917 91 1,512,840 35,427,147 0.678s 16,917 92 1,562,897 36,990,044 0.692s 16,917 93 1,614,050 38,604,094 0.705s 16,917 94 1,666,302 40,270,396 0.720s 16,917 95 1,719,669 41,990,065 0.734s 16,917 96 1,774,166 43,764,231 0.749s 16,917 97 1,829,805 45,594,036 0.767s 16,917 98 1,886,590 47,480,626 0.783s 16,917 99 1,944,540 49,425,166 0.799s 16,917 100 2,003,661 51,428,827 0.816s 16,917 101 2,063,972 53,492,799 0.834s 16,917 102 2,125,486 55,618,285 0.855s 16,917 103 2,188,204 57,806,489 0.873s 16,917 104 2,252,146 60,058,635 0.897s 16,917 105 2,317,319 62,375,954 0.922s 16,917 106 2,383,733 64,759,687 0.944s 16,917 107 2,451,413 67,211,100 0.965s 16,917 108 2,520,360 69,731,460 0.990s 16,917 109 2,590,584 72,322,044 1.010s 16,917 110 2,662,102 74,984,146 1.031s 16,917 111 2,734,927 77,719,073 1.055s 16,917 112 2,809,069 80,528,142 1.082s 16,917 113 2,884,536 83,412,678 1.107s 16,917 114 2,961,346 86,374,024 1.134s 16,917 115 3,039,502 89,413,526 1.158s 16,917 116 3,119,022 92,532,548 1.188s 16,917 117 3,199,918 95,732,466 1.216s 16,917 118 3,282,203 99,014,669 1.243s 16,917 119 3,365,883 102,380,552 1.273s 16,917 120 3,450,981 105,831,533 1.303s 16,917 121 3,537,499 109,369,032 1.332s 16,917 122 3,625,444 112,994,476 1.371s 16,917 123 3,714,838 116,709,314 1.406s 16,917 124 3,805,692 120,515,006 1.435s 16,917 125 3,898,015 124,413,021 1.466s 16,917 126 3,991,818 128,404,839 1.503s 16,917 127 4,087,110 132,491,949 1.536s 16,917 128 4,183,914 136,675,863 1.573s 16,917 129 4,282,228 140,958,091 1.614s 16,917 130 4,382,079 145,340,170 1.654s 16,917 131 4,483,467 149,823,637 1.693s 16,917 132 4,586,405 154,410,042 1.732s 16,917 133 4,690,902 159,100,944 1.770s 16,917 134 4,796,979 163,897,923 1.808s 16,917 135 4,904,646 168,802,569 1.848s 16,917 136 5,013,909 173,816,478 1.887s 16,917 137 5,124,783 178,941,261 1.928s 16,917 138 5,237,275 184,178,536 1.969s 16,917 139 5,351,407 189,529,943 2.012s 16,917 140 5,467,187 194,997,130 2.055s 16,917 141 5,584,624 200,581,754 2.098s 16,917 142 5,703,728 206,285,482 2.143s 16,917 143 5,824,512 212,109,994 2.189s 16,917 144 5,946,992 218,056,986 2.236s 16,917 145 6,071,177 224,128,163 2.284s 16,917 146 6,197,080 230,325,243 2.331s 16,917 147 6,324,708 236,649,951 2.377s 16,917 148 6,454,082 243,104,033 2.426s 16,917 149 6,585,205 249,689,238 2.475s 16,917 150 6,718,091 256,407,329 2.524s 16,917 151 6,852,749 263,260,078 2.577s 16,917 152 6,989,204 270,249,282 2.629s 16,917 153 7,127,454 277,376,736 2.681s 16,917 154 7,267,511 284,644,247 2.736s 16,917 155 7,409,395 292,053,642 2.799s 16,917 156 7,553,112 299,606,754 2.863s 16,917 157 7,698,677 307,305,431 2.926s 16,917 158 7,846,103 315,151,534 2.989s 16,917 159 7,995,394 323,146,928 3.054s 16,917 160 8,146,567 331,293,495 3.125s 16,917 161 8,299,638 339,593,133 3.190s 16,917 162 8,454,607 348,047,740 3.257s 16,917 163 8,611,505 356,659,245 3.324s 16,917 164 8,770,324 365,429,569 3.394s 16,917 165 8,931,081 374,360,650 3.476s 16,917 166 9,093,797 383,454,447 3.546s 16,917 167 9,258,476 392,712,923 3.619s 16,917 168 9,425,127 402,138,050 3.693s 16,917 169 9,593,778 411,731,828 3.766s 16,917 170 9,764,417 421,496,245 3.843s 16,917 171 9,937,068 431,433,313 3.927s 16,917 172 10,111,745 441,545,058 4.003s 16,917 173 10,288,458 451,833,516 4.087s 16,917 174 10,467,215 462,300,731 4.167s 16,917 175 10,648,032 472,948,763 4.245s 16,917 176 10,830,920 483,779,683 4.329s 16,917 177 11,015,896 494,795,579 4.409s 16,917 178 11,202,959 505,998,538 4.493s 16,917 179 11,392,128 517,390,666 4.580s 16,917 180 11,583,420 528,974,086 4.672s 16,917 181 11,776,838 540,750,924 4.760s 16,917 182 11,972,395 552,723,319 4.855s 16,917 183 12,170,108 564,893,427 4.954s 16,917 184 12,369,985 577,263,412 5.047s 16,917 185 12,572,037 589,835,449 5.143s 16,917 186 12,776,285 602,611,734 5.249s 16,917 187 12,982,725 615,594,459 5.348s 16,917 188 13,191,377 628,785,836 5.454s 16,917 189 13,402,256 642,188,092 5.558s 16,917 190 13,615,367 655,803,459 5.667s 16,917 191 13,830,730 669,634,189 5.772s 16,917 192 14,048,347 683,682,536 5.883s 16,917 193 14,268,236 697,950,772 6.002s 16,917 194 14,490,415 712,441,187 6.109s 16,917 195 14,714,880 727,156,067 6.215s 16,917 196 14,941,651 742,097,718 6.324s 16,917 197 15,170,748 757,268,466 6.436s 16,917 198 15,402,165 772,670,631 6.559s 16,917 199 15,635,928 788,306,559 6.684s 16,917 200 15,872,045 804,178,604 6.809s 16,917 201 16,110,527 820,289,131 6.941s 16,917 202 16,351,384 836,640,515 7.068s 16,917 203 16,594,632 853,235,147 7.199s 16,917 204 16,840,283 870,075,430 7.332s 16,917 205 17,088,342 887,163,772 7.462s 16,917 206 17,338,826 904,502,598 7.596s 16,917 207 17,591,739 922,094,337 7.737s 16,917 208 17,847,107 939,941,444 7.868s 16,917 209 18,104,934 958,046,378 8.002s 16,917 210 18,365,234 976,411,612 8.138s 16,917 211 18,628,013 995,039,625 8.275s 16,917 212 18,893,289 1,013,932,914 8.426s 16,917 213 19,161,068 1,033,093,982 8.578s 16,917 214 19,431,375 1,052,525,357 8.727s 16,917 215 19,704,205 1,072,229,562 8.878s 16,917 216 19,979,576 1,092,209,138 9.042s 16,917 217 20,257,500 1,112,466,638 9.199s 16,917 218 20,537,988 1,133,004,626 9.357s 16,917 219 20,821,062 1,153,825,688 9.522s 16,917 220 21,106,720 1,174,932,408 9.680s 16,917 221 21,394,982 1,196,327,390 9.836s 16,917 222 21,685,859 1,218,013,249 9.997s 16,917 223 21,979,347 1,239,992,596 10.162s 16,917 224 22,275,484 1,262,268,080 10.331s 16,917 225 22,574,265 1,284,842,345 10.510s 16,917 226 22,875,700 1,307,718,045 10.700s 16,917 227 23,179,816 1,330,897,861 10.888s 16,917 228 23,486,609 1,354,384,470 11.079s 16,917 229 23,796,098 1,378,180,568 11.262s 16,917 230 24,108,300 1,402,288,868 11.453s 16,917 231 24,423,216 1,426,712,084 11.629s 16,917 232 24,740,870 1,451,452,954 11.809s 16,917 233 25,061,260 1,476,514,214 11.994s 16,917 234 25,384,397 1,501,898,611 12.202s 16,917 235 25,710,307 1,527,608,918 12.406s 16,917 236 26,038,994 1,553,647,912 12.616s 16,917 237 26,370,474 1,580,018,386 12.831s 16,917 238 26,704,760 1,606,723,146 13.049s 16,917 239 27,041,843 1,633,764,989 13.256s 16,917 240 27,381,757 1,661,146,746 13.453s 16,917 241 27,724,512 1,688,871,258 13.655s 16,917 242 28,070,118 1,716,941,376 13.871s 16,917 243 28,418,579 1,745,359,955 14.094s 16,917 244 28,769,910 1,774,129,865 14.315s 16,917 245 29,124,123 1,803,253,988 14.540s 16,917 246 29,481,235 1,832,735,223 14.768s 16,917 247 29,841,260 1,862,576,483 15.005s 16,917 248 30,204,196 1,892,780,679 15.231s 16,917 249 30,570,067 1,923,350,746 15.453s 16,917 250 30,938,881 1,954,289,627 15.694s 16,917 251 31,310,645 1,985,600,272 15.941s 16,917 252 31,685,379 2,017,285,651 16.208s 16,917 253 32,063,093 2,049,348,744 16.456s 16,917 254 32,443,792 2,081,792,536 16.702s 16,917 255 32,827,496 2,114,620,032 16.952s 16,917 2,114,620,032 Total
C++
<lang cpp>#include <iomanip>
- include <iostream>
- include <map>
- include <sstream>
bool isHumble(int i) {
if (i <= 1) return true; if (i % 2 == 0) return isHumble(i / 2); if (i % 3 == 0) return isHumble(i / 3); if (i % 5 == 0) return isHumble(i / 5); if (i % 7 == 0) return isHumble(i / 7); return false;
}
auto toString(int n) {
std::stringstream ss; ss << n; return ss.str();
}
int main() {
auto limit = SHRT_MAX; std::map<int, int> humble; auto count = 0; auto num = 1;
while (count < limit) { if (isHumble(num)) { auto str = toString(num); auto len = str.length(); auto it = humble.find(len);
if (it != humble.end()) { it->second++; } else { humble[len] = 1; }
if (count < 50) std::cout << num << ' '; count++; } num++; } std::cout << "\n\n";
std::cout << "Of the first " << count << " humble numbers:\n"; num = 1; while (num < humble.size() - 1) { auto it = humble.find(num); if (it != humble.end()) { auto c = *it; std::cout << std::setw(5) << c.second << " have " << std::setw(2) << num << " digits\n"; num++; } else { break; } }
return 0;
}</lang>
- Output:
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 32767 humble numbers: 9 have 1 digits 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 1767 have 9 digits
Crystal
Brute force and slow
Checks if each number upto limit is humble number.
<lang ruby>def humble?(i)
return true if (i < 2) return humble?(i // 2) if (i % 2 == 0) return humble?(i // 3) if (i % 3 == 0) return humble?(i // 5) if (i % 5 == 0) return humble?(i // 7) if (i % 7 == 0) false
end
count, num = 0, 0_i64 digits = 10 # max digits for humble numbers limit = 10_i64 ** digits # max numbers to search through humble = Array.new(digits + 1, 0)
while (num += 1) < limit
if humble?(num) humble[num.to_s.size] += 1 print num, " " if count < 50 count += 1 end
end
print "\n\nOf the first #{count} humble numbers:\n" (1..digits).each { |num| printf("%5d have %2d digits\n", humble[num], num) }</lang>
- Output:
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 7574 humble numbers: 9 have 1 digits 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 1767 have 9 digits 2381 have 10 digits
Direct Generation: Orders of magnitude faster
Generate humble numbers directly.
<lang ruby>require "big"
def humble(digits)
h = [1.to_big_i] x2, x3, x5, x7 = 2.to_big_i, 3.to_big_i, 5.to_big_i, 7.to_big_i i, j, k, l = 0, 0, 0, 0 (1..).each do |n| x = {x2, x3, x5, x7}.min # {} tuple|stack faster [] array|heap break if x.to_s.size > digits h << x x2 = 2 * h[i += 1] if x2 == h[n] x3 = 3 * h[j += 1] if x3 == h[n] x5 = 5 * h[k += 1] if x5 == h[n] x7 = 7 * h[l += 1] if x7 == h[n] end h
end
digits = 50 # max digits for humble numbers h = humble(digits) # humble numbers <= digits size count = h.size # the total humble numbers count counts = h.map { |n| n.to_s.size }.tally # hash of digits counts 1..digits print "First 50 Humble Numbers: \n"; (0...50).each { |i| print "#{h[i]} " } print "\n\nOf the first #{count} humble numbers:\n" (1..digits).each { |num| printf("%6d have %2d digits\n", counts[num], num) }</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 Of the first 3363713 humble numbers: 9 have 1 digits 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 1767 have 9 digits 2381 have 10 digits 3113 have 11 digits 3984 have 12 digits 5002 have 13 digits 6187 have 14 digits 7545 have 15 digits 9081 have 16 digits 10815 have 17 digits 12759 have 18 digits 14927 have 19 digits 17323 have 20 digits 19960 have 21 digits 22853 have 22 digits 26015 have 23 digits 29458 have 24 digits 33188 have 25 digits 37222 have 26 digits 41568 have 27 digits 46245 have 28 digits 51254 have 29 digits 56618 have 30 digits 62338 have 31 digits 68437 have 32 digits 74917 have 33 digits 81793 have 34 digits 89083 have 35 digits 96786 have 36 digits 104926 have 37 digits 113511 have 38 digits 122546 have 39 digits 132054 have 40 digits 142038 have 41 digits 152515 have 42 digits 163497 have 43 digits 174986 have 44 digits 187004 have 45 digits 199565 have 46 digits 212675 have 47 digits 226346 have 48 digits 240590 have 49 digits 255415 have 50 digits
D
<lang d>import std.conv; import std.stdio;
bool isHumble(int i) {
if (i <= 1) return true; if (i % 2 == 0) return isHumble(i / 2); if (i % 3 == 0) return isHumble(i / 3); if (i % 5 == 0) return isHumble(i / 5); if (i % 7 == 0) return isHumble(i / 7); return false;
}
void main() {
auto limit = short.max; int[int] humble; auto count = 0; auto num = 1;
while (count < limit) { if (isHumble(num)) { auto str = num.to!string; auto len = str.length; humble[len]++; if (count < 50) write(num, ' '); count++; } num++; } writeln('\n');
writeln("Of the first ", count, " humble numbers:"); num = 1; while (num < humble.length - 1) { if (num in humble) { auto c = humble[num]; writefln("%5d have %2d digits", c, num); num++; } else { break; } }
}</lang>
- Output:
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 32767 humble numbers: 9 have 1 digits 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 1767 have 9 digits
F#
The Functions
<lang fsharp> // Generate humble numbers. Nigel Galloway: June 18th., 2020 let fN g=let mutable n=1UL in (fun()->n<-n*g;n) let fI (n:uint64) g=let mutable q=n in (fun()->let t=q in q<-n*g();t) let fG n g=let mutable vn,vg=n(),g() in fun()->match vg<vn with true->let t=vg in vg<-g();t |_->let t=vn in vn<-n();t let rec fE n=seq{yield n();yield! fE n} let fL n g=let mutable vn,vg,v=n(),g(),None
fun()->match v with Some n->v<-None;n |_->match vg() with r when r<vn->r |r->vg<-fG vg (fI vn (g()));vn<-n();v<-Some r;vg()
let humble = seq{yield 1UL;yield! fE(fL (fN 7UL) (fun()->fL (fN 5UL) (fun()->fL (fN 3UL) (fun()->fN 2UL))))} </lang>
The Tasks
<lang fsharp> humble |> Seq.take 50 |> Seq.iter (printf "%d ");printfn "" </lang>
- Output:
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
<lang fsharp> for n in [1..18] do let g=pown 10UL n in printfn "There are %d humble numbers with %d digits" (humble|>Seq.skipWhile(fun n->n<g/10UL)|>Seq.takeWhile(fun n->n<g)|>Seq.length) n </lang>
- Output:
There are 9 humble numbers with 1 digits There are 36 humble numbers with 2 digits There are 95 humble numbers with 3 digits There are 197 humble numbers with 4 digits There are 356 humble numbers with 5 digits There are 579 humble numbers with 6 digits There are 882 humble numbers with 7 digits There are 1272 humble numbers with 8 digits There are 1767 humble numbers with 9 digits There are 2381 humble numbers with 10 digits There are 3113 humble numbers with 11 digits There are 3984 humble numbers with 12 digits There are 5002 humble numbers with 13 digits There are 6187 humble numbers with 14 digits There are 7545 humble numbers with 15 digits There are 9081 humble numbers with 16 digits There are 10815 humble numbers with 17 digits There are 12759 humble numbers with 18 digits
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
{ #digits initial: 1 } { target initial: 10 } ;
- <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 -- )
[ over target>> >= [ [ 1 + ] change-#digits [ 10 * ] change-target ] when ] [ drop 1 swap [ #digits>> ] [ digits>> ] bi at+ ] bi ;
- ?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 95 upto-n-digits [ .first50 nl ] [ drop .digit-breakdown nl ] [ "Total number of humble numbers found: " write length commas print ] tri ] time ;
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 1,069,748 have 81 digits 1,109,528 have 82 digits 1,150,287 have 83 digits 1,192,035 have 84 digits 1,234,774 have 85 digits 1,278,527 have 86 digits 1,323,301 have 87 digits 1,369,106 have 88 digits 1,415,956 have 89 digits 1,463,862 have 90 digits 1,512,840 have 91 digits 1,562,897 have 92 digits 1,614,050 have 93 digits 1,666,302 have 94 digits 1,719,669 have 95 digits Total number of humble numbers found: 41,990,065 Running time: 335.1803624581294 seconds
Go
Not particularly 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) ten = new(big.Int).SetUint64(10)
)
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 digits := 1 pow10 := new(big.Int).Set(ten) for i := 0; i < len(h); i++ { for { if h[i].Cmp(pow10) >= 0 { pow10.Mul(pow10, ten) digits++ } else { break } } 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
Haskell
<lang haskell>import Data.Set (deleteFindMin, fromList, union) import Data.List.Split (chunksOf) import Data.List (group) import Data.Bool (bool)
HUMBLE NUMBERS ----------------------
humbles :: [Integer] humbles = go $ fromList [1]
where go sofar = x : go (union pruned $ fromList ((x *) <$> [2, 3, 5, 7])) where (x, pruned) = deleteFindMin sofar
-- humbles = filter (all (< 8) . primeFactors) [1 ..]
TEST ---------------------------
main :: IO () main = do
putStrLn "First 50 Humble numbers:" mapM_ (putStrLn . concat) $ chunksOf 10 $ justifyRight 4 ' ' . show <$> take 50 humbles putStrLn "\nCount of humble numbers for each digit length 1-25:" mapM_ print $ take 25 $ ((,) . head <*> length) <$> group (length . show <$> humbles)
DISPLAY -------------------------
justifyRight :: Int -> a -> [a] -> [a] justifyRight n c = (drop . length) <*> (replicate n c ++)</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 Count of humble numbers for each digit length 1-25: (1,9) (2,36) (3,95) (4,197) (5,356) (6,579) (7,882) (8,1272) (9,1767) (10,2381) (11,3113) (12,3984) (13,5002) (14,6187) (15,7545) (16,9081) (17,10815) (18,12759) (19,14927) (20,17323) (21,19960) (22,22853) (23,26015) (24,29458) (25,33188)
J
Multiply all the humble numbers by all the factors appending the next largest value. <lang> humble=: 4 : 0
NB. x humble y generates x humble numbers based on factors y result=. , 1 while. x > # result do. a=. , result */ y result=. result , <./ a #~ a > {: result end.
) </lang>
p: i.4 2 3 5 7 50 humble p: i. 4 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
humbler tests a number for humbleness by deciding if the prime factors are a subset of the given factors.
humbler=: '' -: (-.~ q:) NB. x humbler y tests whether factors of y are a (improper)subset of x 50 {. (#~ (p:i.4)&humbler&>) >: i. 500 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
Use a class to simulate the python generator. This is a more efficient implementation of the first method. <lang> FACTORS_h_=: p: i. 4 HUMBLE_h_=: 1 next_h_=: 3 : 0
result=. <./ HUMBLE i=. HUMBLE i. result HUMBLE=: ~. (((i&{.) , (>:i)&}.) HUMBLE) , result * FACTORS result
) reset_h_=: 3 :'0 $ HUMBLE=: 1' </lang>
3 :0 [ 50 [ reset_h_'' result=.'' for.i.y do. result=. result,next_h_'' end. ) 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
Tally of humble numbers having up to so many digits. Use up to forty thousand humble numbers.
H=: 3 :0 [ 40000 [ reset_h_'' result=.'' for.i.y do. result=. result,next_h_'' end. ) 10^.{:H NB. log of tail is number of digits 15.7432 (,. [: +/ H </ 10&^) i.16 0 0 1 9 2 45 3 140 4 337 5 693 6 1272 7 2154 8 3426 9 5193 10 7574 11 10687 12 14671 13 19673 14 25860 15 33405
Java
<lang java> import java.math.BigInteger; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.HashMap; import java.util.List; import java.util.Map;
public class HumbleNumbers {
public static void main(String[] args) { System.out.println("First 50 humble numbers:"); System.out.println(Arrays.toString(humble(50))); Map<Integer,Integer> lengthCountMap = new HashMap<>(); BigInteger[] seq = humble(1_000_000); for ( int i = 0 ; i < seq.length ; i++ ) { BigInteger humbleNumber = seq[i]; int len = humbleNumber.toString().length(); lengthCountMap.merge(len, 1, (v1, v2) -> v1 + v2); } List<Integer> sorted = new ArrayList<>(lengthCountMap.keySet()); Collections.sort(sorted); System.out.printf("Length Count%n"); for ( Integer len : sorted ) { System.out.printf(" %2s %5s%n", len, lengthCountMap.get(len)); } } private static BigInteger[] humble(int n) { BigInteger two = BigInteger.valueOf(2); BigInteger twoTest = two; BigInteger three = BigInteger.valueOf(3); BigInteger threeTest = three; BigInteger five = BigInteger.valueOf(5); BigInteger fiveTest = five; BigInteger seven = BigInteger.valueOf(7); BigInteger sevenTest = seven; BigInteger[] results = new BigInteger[n]; results[0] = BigInteger.ONE; int twoIndex = 0, threeIndex = 0, fiveIndex = 0, sevenIndex = 0; for ( int index = 1 ; index < n ; index++ ) { results[index] = twoTest.min(threeTest).min(fiveTest).min(sevenTest); if ( results[index].compareTo(twoTest) == 0 ) { twoIndex++; twoTest = two.multiply(results[twoIndex]); } if (results[index].compareTo(threeTest) == 0 ) { threeIndex++; threeTest = three.multiply(results[threeIndex]); } if (results[index].compareTo(fiveTest) == 0 ) { fiveIndex++; fiveTest = five.multiply(results[fiveIndex]); } if (results[index].compareTo(sevenTest) == 0 ) { sevenIndex++; sevenTest = seven.multiply(results[sevenIndex]); } } return results; }
} </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] Length Count 1 9 2 36 3 95 4 197 5 356 6 579 7 882 8 1272 9 1767 10 2381 11 3113 12 3984 13 5002 14 6187 15 7545 16 9081 17 10815 18 12759 19 14927 20 17323 21 19960 22 22853 23 26015 24 29458 25 33188 26 37222 27 41568 28 46245 29 51254 30 56618 31 62338 32 68437 33 74917 34 81793 35 89083 36 96786 37 63955
JavaScript
<lang javascript>(() => {
'use strict';
// ------------------ HUMBLE NUMBERS -------------------
// humbles :: () -> [Int] function* humbles() { // A non-finite stream of Humble numbers. // OEIS A002473 const hs = new Set([1]); while (true) { let nxt = Math.min(...hs) yield nxt; hs.delete(nxt); [2, 3, 5, 7].forEach( x => hs.add(nxt * x) ); } };
// ----------------------- TEST ------------------------ // main :: IO () const main = () => { console.log('First 50 humble numbers:\n') chunksOf(10)(take(50)(humbles())).forEach( row => console.log( concat(row.map(compose(justifyRight(4)(' '), str))) ) ); console.log( '\nCounts of humble numbers of given digit lengths:' ); const counts = map(length)( group(takeWhileGen(x => 11 > x)( fmapGen(x => str(x).length)( humbles() ) )) ); console.log( fTable('\n')(str)(str)( i => counts[i - 1] )(enumFromTo(1)(10)) ); };
// ----------------- GENERIC FUNCTIONS -----------------
// chunksOf :: Int -> [a] -> a const chunksOf = n => xs => enumFromThenTo(0)(n)( xs.length - 1 ).reduce( (a, i) => a.concat([xs.slice(i, (n + i))]), [] );
// compose (<<<) :: (b -> c) -> (a -> b) -> a -> c const compose = (...fs) => // A function defined by the right-to-left // composition of all the functions in fs. fs.reduce( (f, g) => x => f(g(x)), x => x );
// concat :: a -> [a] // concat :: [String] -> String const concat = xs => 0 < xs.length ? (() => { const unit = 'string' !== typeof xs[0] ? ( [] ) : ; return unit.concat.apply(unit, xs); })() : [];
// enumFromThenTo :: Int -> Int -> Int -> [Int] const enumFromThenTo = x1 => x2 => y => { const d = x2 - x1; return Array.from({ length: Math.floor(y - x2) / d + 2 }, (_, i) => x1 + (d * i)); };
// enumFromTo :: Int -> Int -> [Int] const enumFromTo = m => n => Array.from({ length: 1 + n - m }, (_, i) => m + i);
// fTable :: String -> (a -> String) -> (b -> String) // -> (a -> b) -> [a] -> String const fTable = s => xShow => fxShow => f => xs => { // Heading -> x display function -> // fx display function -> // f -> values -> tabular string const ys = xs.map(xShow), w = Math.max(...ys.map(length)); return s + '\n' + zipWith( a => b => a.padStart(w, ' ') + ' -> ' + b )(ys)( xs.map(x => fxShow(f(x))) ).join('\n'); };
// fmapGen <$> :: (a -> b) -> Gen [a] -> Gen [b] const fmapGen = f => function*(gen) { let v = take(1)(gen); while (0 < v.length) { yield(f(v[0])) v = take(1)(gen) } };
// group :: Eq a => [a] -> a const group = xs => { // A list of lists, each containing only equal elements, // such that the concatenation of these lists is xs. const go = xs => 0 < xs.length ? (() => { const h = xs[0], i = xs.findIndex(x => h !== x); return i !== -1 ? ( [xs.slice(0, i)].concat(go(xs.slice(i))) ) : [xs]; })() : []; const v = go(list(xs)); return 'string' === typeof xs ? ( v.map(x => x.join()) ) : v; };
// justifyRight :: Int -> Char -> String -> String const justifyRight = n => // The string s, preceded by enough padding (with // the character c) to reach the string length n. c => s => n > s.length ? ( s.padStart(n, c) ) : s;
// length :: [a] -> Int const length = xs => // Returns Infinity over objects without finite length. // This enables zip and zipWith to choose the shorter // argument when one is non-finite, like cycle, repeat etc (Array.isArray(xs) || 'string' === typeof xs) ? ( xs.length ) : Infinity;
// list :: StringOrArrayLike b => b -> [a] const list = xs => // xs itself, if it is an Array, // or an Array derived from xs. Array.isArray(xs) ? ( xs ) : Array.from(xs);
// map :: (a -> b) -> [a] -> [b] const map = f => // The list obtained by applying f // to each element of xs. // (The image of xs under f). xs => [...xs].map(f);
// str :: a -> String const str = x => x.toString();
// take :: Int -> [a] -> [a] // take :: Int -> String -> String const take = n => xs => 'GeneratorFunction' !== xs.constructor.constructor.name ? ( xs.slice(0, n) ) : [].concat.apply([], Array.from({ length: n }, () => { const x = xs.next(); return x.done ? [] : [x.value]; }));
// takeWhileGen :: (a -> Bool) -> Gen [a] -> [a] const takeWhileGen = p => xs => { const ys = []; let nxt = xs.next(), v = nxt.value; while (!nxt.done && p(v)) { ys.push(v); nxt = xs.next(); v = nxt.value } return ys; };
// zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] const zipWith = f => // Use of `take` and `length` here allows zipping with non-finite lists // i.e. generators like cycle, repeat, iterate. xs => ys => { const n = Math.min(length(xs), length(ys)); return Infinity > n ? ( (([as, bs]) => Array.from({ length: n }, (_, i) => f(as[i])( bs[i] )))([xs, ys].map( compose(take(n), list) )) ) : zipWithGen(f)(xs)(ys); };
// MAIN --- return main();
})();</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 Counts of humble numbers of given digit lengths: 1 -> 9 2 -> 36 3 -> 95 4 -> 197 5 -> 356 6 -> 579 7 -> 882 8 -> 1272 9 -> 1767 10 -> 2381
Julia
To spare heap memory, keeps only the last 2 million values found for use in the generation of further values. <lang julia> function counthumbledigits(maxdigits, returnsequencelength=50)
n, count, adjustindex, maxdiff = BigInt(1), 0, BigInt(0), 0 humble, savesequence = Vector{BigInt}([1]), Vector{BigInt}() base2, base3, base5, base7 = 1, 1, 1, 1 next2, next3, next5, next7 = BigInt(2), BigInt(3), BigInt(5), BigInt(7) digitcounts= Dict{Int, Int}(1 => 1) while n < BigInt(10)^(maxdigits+1) n = min(next2, next3, next5, next7) push!(humble, n) count += 1 if count == returnsequencelength savesequence = deepcopy(humble[1:returnsequencelength]) elseif count > 2000000 popfirst!(humble) adjustindex += 1 end placesbase10 = length(string(n)) if haskey(digitcounts, placesbase10) digitcounts[placesbase10] += 1 else digitcounts[placesbase10] = 1 end maxdiff = max(maxdiff, count - base2, count - base3, count - base5, count - base7) (next2 <= n) && (next2 = 2 * humble[(base2 += 1) - adjustindex]) (next3 <= n) && (next3 = 3 * humble[(base3 += 1) - adjustindex]) (next5 <= n) && (next5 = 5 * humble[(base5 += 1) - adjustindex]) (next7 <= n) && (next7 = 7 * humble[(base7 += 1) - adjustindex]) end savesequence, digitcounts, count, maxdiff
end
counthumbledigits(3)
@time first120, digitcounts, count, maxdiff = counthumbledigits(99)
println("\nTotal humble numbers counted: $count") println("Maximum depth between top of array and a multiplier: $maxdiff\n")
println("The first 50 humble numbers are: $first120\n\nDigit counts of humble numbers:") for ndigits in sort(collect(keys(digitcounts)))[1:end-1]
println(lpad(digitcounts[ndigits], 10), " have ", lpad(ndigits, 3), " digits.")
end
</lang>
- Output:
828.693164 seconds (3.61 G allocations: 64.351 GiB, 51.37% gc time) Total humble numbers counted: 51428827 Maximum depth between top of array and a multiplier: 1697189 The first 50 humble numbers are: BigInt[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] Digit counts of humble numbers: 9 have 1 digits. 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. 1767 have 9 digits. 2381 have 10 digits. 3113 have 11 digits. 3984 have 12 digits. 5002 have 13 digits. 6187 have 14 digits. 7545 have 15 digits. 9081 have 16 digits. 10815 have 17 digits. 12759 have 18 digits. 14927 have 19 digits. 17323 have 20 digits. 19960 have 21 digits. 22853 have 22 digits. 26015 have 23 digits. 29458 have 24 digits. 33188 have 25 digits. 37222 have 26 digits. 41568 have 27 digits. 46245 have 28 digits. 51254 have 29 digits. 56618 have 30 digits. 62338 have 31 digits. 68437 have 32 digits. 74917 have 33 digits. 81793 have 34 digits. 89083 have 35 digits. 96786 have 36 digits. 104926 have 37 digits. 113511 have 38 digits. 122546 have 39 digits. 132054 have 40 digits. 142038 have 41 digits. 152515 have 42 digits. 163497 have 43 digits. 174986 have 44 digits. 187004 have 45 digits. 199565 have 46 digits. 212675 have 47 digits. 226346 have 48 digits. 240590 have 49 digits. 255415 have 50 digits. 270843 have 51 digits. 286880 have 52 digits. 303533 have 53 digits. 320821 have 54 digits. 338750 have 55 digits. 357343 have 56 digits. 376599 have 57 digits. 396533 have 58 digits. 417160 have 59 digits. 438492 have 60 digits. 460533 have 61 digits. 483307 have 62 digits. 506820 have 63 digits. 531076 have 64 digits. 556104 have 65 digits. 581902 have 66 digits. 608483 have 67 digits. 635864 have 68 digits. 664053 have 69 digits. 693065 have 70 digits. 722911 have 71 digits. 753593 have 72 digits. 785141 have 73 digits. 817554 have 74 digits. 850847 have 75 digits. 885037 have 76 digits. 920120 have 77 digits. 956120 have 78 digits. 993058 have 79 digits. 1030928 have 80 digits. 1069748 have 81 digits. 1109528 have 82 digits. 1150287 have 83 digits. 1192035 have 84 digits. 1234774 have 85 digits. 1278527 have 86 digits. 1323301 have 87 digits. 1369106 have 88 digits. 1415956 have 89 digits. 1463862 have 90 digits. 1512840 have 91 digits. 1562897 have 92 digits. 1614050 have 93 digits. 1666302 have 94 digits. 1719669 have 95 digits. 1774166 have 96 digits. 1829805 have 97 digits. 1886590 have 98 digits. 1944540 have 99 digits. 2003661 have 100 digits.
Kotlin
<lang scala>fun isHumble(i: Int): Boolean {
if (i <= 1) return true if (i % 2 == 0) return isHumble(i / 2) if (i % 3 == 0) return isHumble(i / 3) if (i % 5 == 0) return isHumble(i / 5) if (i % 7 == 0) return isHumble(i / 7) return false
}
fun main() {
val limit: Int = Short.MAX_VALUE.toInt() val humble = mutableMapOf<Int, Int>() var count = 0 var num = 1
while (count < limit) { if (isHumble(num)) { val str = num.toString() val len = str.length humble.merge(len, 1) { a, b -> a + b }
if (count < 50) print("$num ") count++ } num++ } println("\n")
println("Of the first $count humble numbers:") num = 1 while (num < humble.size - 1) { if (humble.containsKey(num)) { val c = humble[num] println("%5d have %2d digits".format(c, num)) num++ } else { break } }
}</lang>
- Output:
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 32767 humble numbers: 9 have 1 digits 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 1767 have 9 digits
Lua
<lang lua>function isHumble(n)
local n2 = math.floor(n)
if n2 <= 1 then return true end if n2 % 2 == 0 then return isHumble(n2 / 2) end if n2 % 3 == 0 then return isHumble(n2 / 3) end if n2 % 5 == 0 then return isHumble(n2 / 5) end if n2 % 7 == 0 then return isHumble(n2 / 7) end
return false
end
function main()
local limit = 10000 local humble = {0, 0, 0, 0, 0, 0, 0, 0, 0} local count = 0 local num = 1
while count < limit do if isHumble(num) then local buffer = string.format("%d", num) local le = string.len(buffer) if le > 9 then break end humble[le] = humble[le] + 1
if count < 50 then io.write(num .. " ") end count = count + 1 end num = num + 1 end print("\n")
print("Of the first " .. count .. " humble numbers:") for num=1,9 do print(string.format("%5d have %d digits", humble[num], num)) end
end
main()</lang>
- Output:
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 5193 humble numbers: 9 have 1 digits 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 1767 have 9 digits
Pascal
modification of hamming-numbers http://rosettacode.org/wiki/Hamming_numbers#a_fast_alternative
Check for the first occurrence of 2^i/5^i -> 10^i
Using float80/extended and float64/double and single/float32 version, to get a possibility to check values.
Up to 877 digits I was able to compare, than float80 run out of memory (13.5 Gb )
float80 and float64 got same values up to 877.float64 is 2,3x faster than float80
float32 get wrong at 37 digits,->37 104925 instead of 104926
runtime: 2 x digits => ~ runtime 2^4
<lang pascal>
{$IFDEF FPC}
{$MODE DELPHI} {$OPTIMIZATION ON,ALL} {$CODEALIGN proc=32,loop=1} {$ALIGN 16}
{$ELSE}
{$APPTYPE CONSOLE}
{$ENDIF} uses
sysutils;
const
//PlInit(4); <= maxPrimFakCnt+1 maxPrimFakCnt = 3;//3,7,11 to keep data 8-Byte aligned minElemCnt = 10;
type
tPrimList = array of NativeUint; tnumber = extended; tpNumber= ^tnumber; tElem = record n : tnumber;//ln(prime[0]^Pots[0]*... dummy: array[0..5] of byte;//extend extended to 16 byte Pots: array[0..maxPrimFakCnt] of word; end; tpElem = ^tElem; tElems = array of tElem; tElemArr = array [0..0] of tElem; tpElemArr = ^tElemArr;
tpFaktorRec = ^tFaktorRec; tFaktorRec = record frElems : tElems; frInsElems: tElems; frAktIdx : NativeUint; frMaxIdx : NativeUint; frPotNo : NativeUint; frActPot : NativeUint; frNextFr : tpFaktorRec; frActNumb: tElem; frLnPrime: tnumber; end; tArrFR = array of tFaktorRec;
//LoE == List of Elements function LoEGetNextElement(pFR :tpFaktorRec):tElem;forward;
var
Pl : tPrimList; ActIndex : NativeUint; ArrInsert : tElems;
procedure PlInit(n: integer); const
cPl : array[0..11] of byte=(2,3,5,7,11,13,17,19,23,29,31,37);
var
i : integer;
Begin
IF n>High(cPl)+1 then n := High(cPl) else IF n < 0 then n := 1; IF maxPrimFakCnt+1 < n then Begin writeln(' Need to compile with bigger maxPrimFakCnt '); Halt(0); end; setlength(Pl,n); dec(n); For i := 0 to n do Pl[i] := cPl[i];
end;
procedure AusgabeElem(pElem: tElem;ShowPot:Boolean=false); var
i : integer;
Begin
with pElem do Begin IF n < 23 then write(round(exp(n)),' ') else write('ln ',n:13:7); IF ShowPot then Begin For i := 0 to maxPrimFakCnt do write(' ',PL[i]:2,'^',Pots[i]); writeln end; end;
end;
procedure LoECreate(const Pl: tPrimList;var FA:tArrFR); var
i : integer;
Begin
setlength(ArrInsert,100); setlength(FA,Length(PL)); For i := 0 to High(PL) do with FA[i] do Begin //automatic zeroing IF i < High(PL) then Begin setlength(frElems,minElemCnt); setlength(frInsElems,minElemCnt); frNextFr := @FA[i+1] end else Begin setlength(frElems,2); setlength(frInsElems,0); frNextFr := NIL; end; frPotNo := i; frLnPrime:= ln(PL[i]); frMaxIdx := 0; frAktIdx := 0; frActPot := 1; With frElems[0] do Begin n := frLnPrime; Pots[i]:= 1; end; frActNumb := frElems[0]; end; ActIndex := 0;
end;
procedure LoEFree(var FA:tArrFR);
var
i : integer;
Begin
For i := High(FA) downto Low(FA) do setlength(FA[i].frElems,0); setLength(FA,0);
end;
function LoEGetActElem(pFr:tpFaktorRec):tElem;inline; Begin
with pFr^ do result := frElems[frAktIdx];
end;
function LoEGetActLstNumber(pFr:tpFaktorRec):tpNumber;inline; Begin
with pFr^ do result := @frElems[frAktIdx].n;
end;
procedure LoEIncInsArr(var a:tElems); Begin
setlength(a,Length(a)*8 div 5);
end;
procedure LoEIncreaseElems(pFr:tpFaktorRec;minCnt:NativeUint); var
newLen: NativeUint;
Begin
with pFR^ do begin newLen := Length(frElems); minCnt := minCnt+frMaxIdx; repeat newLen := newLen*8 div 5 +1; until newLen > minCnt; setlength(frElems,newLen); end;
end;
procedure LoEInsertNext(pFr:tpFaktorRec;Limit:tnumber); var
pNum : tpNumber; pElems : tpElemArr; cnt,i,u : NativeInt;
begin
with pFr^ do Begin //collect numbers of heigher primes cnt := 0; pNum := LoEGetActLstNumber(frNextFr); while Limit > pNum^ do Begin frInsElems[cnt] := LoEGetNextElement(frNextFr); inc(cnt); IF cnt > High(frInsElems) then LoEIncInsArr(frInsElems); pNum := LoEGetActLstNumber(frNextFr); end;
if cnt = 0 then EXIT;
i := frMaxIdx; u := frMaxIdx+cnt+1;
IF u > High(frElems) then LoEIncreaseElems(pFr,cnt);
IF frPotNo = 0 then inc(ActIndex,u); //Merge pElems := @frElems[0]; dec(cnt); dec(u); frMaxIdx:= u; repeat IF pElems^[i].n < frInsElems[cnt].n then Begin pElems^[u] := frInsElems[cnt]; dec(cnt); end else Begin pElems^[u] := pElems^[i]; dec(i); end; dec(u); until (i<0) or (cnt<0); IF i < 0 then For u := cnt downto 0 do pElems^[u] := frInsElems[u]; end;
end;
procedure LoEAppendNext(pFr:tpFaktorRec;Limit:tnumber); var
pNum : tpNumber; pElems : tpElemArr; i : NativeInt;
begin
with pFr^ do Begin i := frMaxIdx+1; pElems := @frElems[0]; pNum := LoEGetActLstNumber(frNextFr); while Limit > pNum^ do Begin IF i > High(frElems) then Begin LoEIncreaseElems(pFr,10); pElems := @frElems[0]; end; pElems^[i] := LoEGetNextElement(frNextFr); inc(i); pNum := LoEGetActLstNumber(frNextFr); end; inc(ActIndex,i); frMaxIdx:= i-1; end;
end;
procedure LoENextList(pFr:tpFaktorRec); var
pElems : tpElemArr; j,PotNum : NativeInt; lnPrime : tnumber;
begin
with pFR^ do Begin //increase all Elements by factor pElems := @frElems[0]; LnPrime := frLnPrime; PotNum := frPotNo; for j := frMaxIdx Downto 0 do with pElems^[j] do Begin n := LnPrime+n; inc(Pots[PotNum]); end; //x^j -> x^(j+1) j := frActPot+1; with frActNumb do begin n:= j*LnPrime; Pots[PotNum]:= j; end; frActPot := j; //if something follows IF frNextFr <> NIL then LoEInsertNext(pFR,frActNumb.n); frAktIdx := 0; end;
end;
function LoEGetNextElementPointer(pFR :tpFaktorRec):tpElem; Begin
with pFr^ do Begin IF frMaxIdx < frAktIdx then LoENextList(pFr); result := @frElems[frAktIdx]; inc(frAktIdx); inc(ActIndex); end;
end;
function LoEGetNextElement(pFR :tpFaktorRec):tElem; Begin
with pFr^ do Begin result := frElems[frAktIdx]; inc(frAktIdx); IF frMaxIdx < frAktIdx then LoENextList(pFr); inc(ActIndex); end;
end;
function LoEGetNextNumber(pFR :tpFaktorRec):tNumber; Begin
with pFr^ do Begin result := frElems[frAktIdx].n; inc(frAktIdx); IF frMaxIdx < frAktIdx then LoENextList(pFr); inc(ActIndex); end;
end;
procedure LoEGetNumber(pFR :tpFaktorRec;no:NativeUint); Begin
dec(no); while ActIndex < no do LoENextList(pFR); with pFr^ do frAktIdx := (no-(ActIndex-frMaxIdx)-1);
end;
procedure first50; var
FA: tArrFR; i : integer;
Begin
LoECreate(Pl,FA); write(1,' '); For i := 1 to 49 do AusgabeElem(LoEGetNextElement(@FA[0])); writeln; LoEFree(FA);
end;
procedure GetDigitCounts(MaxDigit:Uint32); var
T1,T0 : TDateTime; FA: tArrFR; i,j,LastCnt : NativeUint;
Begin
T0 := now; inc(MaxDigit); LoECreate(Pl,FA); i := 1; j := 0; writeln('Digits count total count '); repeat LastCnt := j; repeat inc(j); with LoEGetNextElementPointer(@FA[0])^ do IF (Pots[2]= i) AND (Pots[0]= i) then break; until false; writeln(i:4,j-LastCnt:12,j:15,(now-T0)*86.6e3:10:3,' s'); LastCnt := j; inc(i); until i = MaxDigit; LoEFree(FA); T1 := now; writeln('Total number of humble numbers found: ',j); writeln('Running time: ',(T1-T0)*86.6e6:0:0,' ms');
end;
Begin
//check if PlInit(4); <= maxPrimFakCnt+1 PlInit(4);// 3 -> 2,3,5/ 4 -> 2,3,5,7 first50; GetDigitCounts(100);
End.</lang>
- Output:
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 Digits count total count 1 9 9 0.000 s 2 36 45 0.000 s 3 95 140 0.000 s 4 197 337 0.000 s 5 356 693 0.001 s 6 579 1272 0.001 s 7 882 2154 0.001 s 8 1272 3426 0.001 s 9 1767 5193 0.001 s 10 2381 7574 0.001 s 11 3113 10687 0.001 s 12 3984 14671 0.001 s 13 5002 19673 0.001 s 14 6187 25860 0.002 s 15 7545 33405 0.002 s 16 9081 42486 0.003 s 17 10815 53301 0.003 s 18 12759 66060 0.004 s 19 14927 80987 0.004 s 20 17323 98310 0.005 s 21 19960 118270 0.006 s 22 22853 141123 0.007 s 23 26015 167138 0.008 s 24 29458 196596 0.009 s 25 33188 229784 0.009 s 26 37222 267006 0.010 s 27 41568 308574 0.011 s 28 46245 354819 0.011 s 29 51254 406073 0.012 s 30 56618 462691 0.013 s 31 62338 525029 0.014 s 32 68437 593466 0.015 s 33 74917 668383 0.016 s 34 81793 750176 0.018 s 35 89083 839259 0.019 s 36 96786 936045 0.021 s 37 104926 1040971 0.022 s 38 113511 1154482 0.025 s 39 122546 1277028 0.027 s 40 132054 1409082 0.028 s 41 142038 1551120 0.031 s 42 152515 1703635 0.033 s 43 163497 1867132 0.036 s 44 174986 2042118 0.039 s 45 187004 2229122 0.042 s 46 199565 2428687 0.045 s 47 212675 2641362 0.050 s 48 226346 2867708 0.053 s 49 240590 3108298 0.056 s 50 255415 3363713 0.061 s 51 270843 3634556 0.065 s 52 286880 3921436 0.070 s 53 303533 4224969 0.076 s 54 320821 4545790 0.081 s 55 338750 4884540 0.087 s 56 357343 5241883 0.094 s 57 376599 5618482 0.100 s 58 396533 6015015 0.106 s 59 417160 6432175 0.113 s 60 438492 6870667 0.122 s 61 460533 7331200 0.130 s 62 483307 7814507 0.137 s 63 506820 8321327 0.148 s 64 531076 8852403 0.156 s 65 556104 9408507 0.165 s 66 581902 9990409 0.177 s 67 608483 10598892 0.186 s 68 635864 11234756 0.197 s 69 664053 11898809 0.210 s 70 693065 12591874 0.222 s 71 722911 13314785 0.235 s 72 753593 14068378 0.250 s 73 785141 14853519 0.262 s 74 817554 15671073 0.275 s 75 850847 16521920 0.292 s 76 885037 17406957 0.305 s 77 920120 18327077 0.320 s 78 956120 19283197 0.338 s 79 993058 20276255 0.354 s 80 1030928 21307183 0.370 s 81 1069748 22376931 0.391 s 82 1109528 23486459 0.409 s 83 1150287 24636746 0.428 s 84 1192035 25828781 0.451 s 85 1234774 27063555 0.470 s 86 1278527 28342082 0.490 s 87 1323301 29665383 0.516 s 88 1369106 31034489 0.538 s 89 1415956 32450445 0.559 s 90 1463862 33914307 0.582 s 91 1512840 35427147 0.612 s 92 1562897 36990044 0.636 s 93 1614050 38604094 0.662 s 94 1666302 40270396 0.694 s 95 1719669 41990065 0.721 s 96 1774166 43764231 0.748 s 97 1829805 45594036 0.785 s 98 1886590 47480626 0.815 s 99 1944540 49425166 0.845 s 100 2003661 51428827 0.884 s 101 2063972 53492799 0.916 s 102 2125486 55618285 0.948 s 103 2188204 57806489 0.991 s 104 2252146 60058635 1.026 s 105 2317319 62375954 1.062 s 106 2383733 64759687 1.110 s 107 2451413 67211100 1.147 s 108 2520360 69731460 1.186 s 109 2590584 72322044 1.237 s 110 2662102 74984146 1.278 s .. shortened 120 3450981 105831533 1.795 s 130 4382079 145340170 2.450 s 140 5467187 194997130 3.298 s 150 6718091 256407329 4.318 s 170 9764417 421496245 7.055 s 180 11583420 528974086 8.822 s 190 13615367 655803459 10.972 s 200 15872045 804178604 13.424 s 300 53391941 4039954757 66.882 s 400 126350163 12719142480 207.622 s 500 246533493 30980806733 503.269 s 600 425728730 64142692268 1039.928 s 700 675722681 118701223590 1920.325 s 800 1008302151 202331504969 3265.469 s .. 876 1323548095 290737888948 4690.230 s 877 1328082553 292065971501 4709.931 s
Perl
<lang perl>use strict; use warnings; use List::Util 'min';
- use bigint # works, but slow
use Math::GMPz; # this module gives roughly 16x speed-up
sub humble_gen {
my @s = ([1], [1], [1], [1]); my @m = (2, 3, 5, 7); @m = map { Math::GMPz->new($_) } @m; # comment out to NOT use Math::GMPz
return sub { my $n = min $s[0][0], $s[1][0], $s[2][0], $s[3][0]; for (0..3) { shift @{$s[$_]} if $s[$_][0] == $n; push @{$s[$_]}, $n * $m[$_] } return $n }
}
my $h = humble_gen; my $i = 0; my $upto = 50;
my $list; ++$i, $list .= $h->(). " " until $i == $upto; print "$list\n";
$h = humble_gen; # from the top... my $count = 0; my $digits = 1;
while ($digits <= $upto) {
++$count and next if $digits == length $h->(); printf "Digits: %2d - Count: %s\n", $digits++, $count; $count = 1;
}</lang>
- Output:
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 Digits: 1 - Count: 9 Digits: 2 - Count: 36 Digits: 3 - Count: 95 Digits: 4 - Count: 197 Digits: 5 - Count: 356 Digits: 6 - Count: 579 Digits: 7 - Count: 882 Digits: 8 - Count: 1272 Digits: 9 - Count: 1767 Digits: 10 - Count: 2381 Digits: 11 - Count: 3113 Digits: 12 - Count: 3984 Digits: 13 - Count: 5002 Digits: 14 - Count: 6187 Digits: 15 - Count: 7545 Digits: 16 - Count: 9081 Digits: 17 - Count: 10815 Digits: 18 - Count: 12759 Digits: 19 - Count: 14927 Digits: 20 - Count: 17323 Digits: 21 - Count: 19960 Digits: 22 - Count: 22853 Digits: 23 - Count: 26015 Digits: 24 - Count: 29458 Digits: 25 - Count: 33188 Digits: 26 - Count: 37222 Digits: 27 - Count: 41568 Digits: 28 - Count: 46245 Digits: 29 - Count: 51254 Digits: 30 - Count: 56618 Digits: 31 - Count: 62338 Digits: 32 - Count: 68437 Digits: 33 - Count: 74917 Digits: 34 - Count: 81793 Digits: 35 - Count: 89083 Digits: 36 - Count: 96786 Digits: 37 - Count: 104926 Digits: 38 - Count: 113511 Digits: 39 - Count: 122546 Digits: 40 - Count: 132054 Digits: 41 - Count: 142038 Digits: 42 - Count: 152515 Digits: 43 - Count: 163497 Digits: 44 - Count: 174986 Digits: 45 - Count: 187004 Digits: 46 - Count: 199565 Digits: 47 - Count: 212675 Digits: 48 - Count: 226346 Digits: 49 - Count: 240590 Digits: 50 - Count: 255415
Phix
I felt pretty good about the performance of this, until I ran the Go version - humbled indeed!
It will go all the way to 100 digits if you give it time (18 mins, on 64bit - 32bit runs out of memory after printing the 99th line)
I also tried a log version (similar to Hamming_numbers) but inaccuracies with floor(h[n][LOG]) crept in quite early, at just 10 digits.
<lang Phix>-- demo/rosetta/humble.exw
include mpfr.e
procedure humble(integer n, bool countdigits=false) -- if countdigits is false: show first n humble numbers, -- if countdigits is true: count them up to n digits.
sequence humble = {mpz_init(1)}, nexts = {2,3,5,7}, indices = repeat(1,4) for i=1 to 4 do nexts[i] = mpz_init(nexts[i]) end for integer digits = 1, count = 1, dead = 1, tc = 0 atom t0 = time() mpz p10 = mpz_init(10) while ((not countdigits) and length(humble)<n) or (countdigits and digits<=n) do mpz x = mpz_init_set(mpz_min(nexts)) humble = append(humble,x) if countdigits then if mpz_cmp(x,p10)>=0 then mpz_mul_si(p10,p10,10) integer d = min(indices) for k=dead to d-1 do humble[k] = mpz_free(humble[k]) end for dead = d string s = iff(digits=1?"":"s"), e = elapsed(time()-t0) tc += count
-- e &= sprintf(", %,d dead",{dead-1})
e &= sprintf(", total:%,d",{tc}) printf(1,"%,12d humble numbers have %d digit%s (%s)\n",{count,digits,s,e}) digits += 1 count = 1 else count += 1 end if end if for j=1 to 4 do if mpz_cmp(nexts[j],x)<=0 then indices[j] += 1 mpz_mul_si(nexts[j],humble[indices[j]],get_prime(j)) end if end for end while if not countdigits then for i=1 to length(humble) do humble[i] = shorten(mpz_get_str(humble[i]),ml:=10) end for printf(1,"First %d humble numbers: %s\n\n",{n,join(humble," ")}) end if
end procedure
humble(50) humble(42,true)</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 9 humble numbers have 1 digit (0s, total:9) 36 humble numbers have 2 digits (0s, total:45) 95 humble numbers have 3 digits (0s, total:140) 197 humble numbers have 4 digits (0s, total:337) 356 humble numbers have 5 digits (0s, total:693) 579 humble numbers have 6 digits (0.0s, total:1,272) 882 humble numbers have 7 digits (0.0s, total:2,154) 1,272 humble numbers have 8 digits (0.0s, total:3,426) 1,767 humble numbers have 9 digits (0.1s, total:5,193) 2,381 humble numbers have 10 digits (0.1s, total:7,574) 3,113 humble numbers have 11 digits (0.2s, total:10,687) 3,984 humble numbers have 12 digits (0.2s, total:14,671) 5,002 humble numbers have 13 digits (0.3s, total:19,673) 6,187 humble numbers have 14 digits (0.4s, total:25,860) 7,545 humble numbers have 15 digits (0.5s, total:33,405) 9,081 humble numbers have 16 digits (0.6s, total:42,486) 10,815 humble numbers have 17 digits (0.8s, total:53,301) 12,759 humble numbers have 18 digits (0.9s, total:66,060) 14,927 humble numbers have 19 digits (1.2s, total:80,987) 17,323 humble numbers have 20 digits (1.4s, total:98,310) 19,960 humble numbers have 21 digits (1.7s, total:118,270) 22,853 humble numbers have 22 digits (2.0s, total:141,123) 26,015 humble numbers have 23 digits (2.3s, total:167,138) 29,458 humble numbers have 24 digits (2.7s, total:196,596) 33,188 humble numbers have 25 digits (3.2s, total:229,784) 37,222 humble numbers have 26 digits (3.7s, total:267,006) 41,568 humble numbers have 27 digits (4.3s, total:308,574) 46,245 humble numbers have 28 digits (5.0s, total:354,819) 51,254 humble numbers have 29 digits (5.7s, total:406,073) 56,618 humble numbers have 30 digits (6.5s, total:462,691) 62,338 humble numbers have 31 digits (7.3s, total:525,029) 68,437 humble numbers have 32 digits (8.3s, total:593,466) 74,917 humble numbers have 33 digits (9.4s, total:668,383) 81,793 humble numbers have 34 digits (10.5s, total:750,176) 89,083 humble numbers have 35 digits (11.7s, total:839,259) 96,786 humble numbers have 36 digits (13.1s, total:936,045) 104,926 humble numbers have 37 digits (14.6s, total:1,040,971) 113,511 humble numbers have 38 digits (16.2s, total:1,154,482) 122,546 humble numbers have 39 digits (17.9s, total:1,277,028) 132,054 humble numbers have 40 digits (19.7s, total:1,409,082) 142,038 humble numbers have 41 digits (21.7s, total:1,551,120) 152,515 humble numbers have 42 digits (23.9s, total:1,703,635)
PL/M
Tested using a PLM286 to C converter and a suitable I/O library. <lang plm>HUMBLE: DO;
/* find some Humble numbers - numbers with no prime factors above 7 */ /* External I/O procedures */ WRITE$STRING: PROCEDURE( S ) EXTERNAL; DECLARE S POINTER; END; WRITE$WORD: PROCEDURE( W ) EXTERNAL; DECLARE W WORD; END; WRITE$NL: PROCEDURE EXTERNAL; END; /* End external I/O procedures */ DECLARE MAX$HUMBLE LITERALLY '400'; /* returns the minimum of a and b */ MIN: PROCEDURE( A, B ) WORD; DECLARE ( A, B ) WORD; IF A < B THEN RETURN( A ); ELSE RETURN( B ); END MIN; /* display a statistic about Humble numbers */ WRITEHSTAT: PROCEDURE( S, D ); DECLARE ( S, D ) WORD; CALL WRITE$STRING( @( 'there are', 0 ) ); CALL WRITE$WORD( S ); CALL WRITE$STRING( @( ' Humble numbers with ', 0 ) ); CALL WRITE$WORD( D ); CALL WRITE$STRING( @( ' digit', 0 ) ); IF D > 1 THEN CALL WRITE$STRING( @( 's', 0 ) ); CALL WRITE$NL(); END WRITEHSTAT; /* find and print Humble Numbers */ MAIN: PROCEDURE; DECLARE H( MAX$HUMBLE ) WORD; DECLARE ( P2, P3, P5, P7, M , LAST2, LAST3, LAST5, LAST7 , H1, H2, H3, H4, H5, H6, HPOS ) WORD; /* 1 is the first Humble number */ H( 0 ) = 1; H1 = 0; H2 = 0; H3 = 0; H4 = 0; H5 = 0; H6 = 0; LAST2 = 0; LAST3 = 0; LAST5 = 0; LAST7 = 0; P2 = 2; P3 = 3; P5 = 5; P7 = 7; DO HPOS = 1 TO MAX$HUMBLE - 1; /* the next Humble number is the lowest of the next multiple */ /* of 2, 3, 5, 7 */ M = MIN( MIN( MIN( P2, P3 ), P5 ), P7 ); H( HPOS ) = M; IF M = P2 THEN DO; /* the Humble number was the next multiple of 2 */ /* the next multiple of 2 will now be twice the Humble */ /* number following the previous multple of 2 */ LAST2 = LAST2 + 1; P2 = 2 * H( LAST2 ); END; IF M = P3 THEN DO; LAST3 = LAST3 + 1; P3 = 3 * H( LAST3 ); END; IF M = P5 THEN DO; LAST5 = LAST5 + 1; P5 = 5 * H( LAST5 ); END; IF M = P7 THEN DO; LAST7 = LAST7 + 1; P7 = 7 * H( LAST7 ); END; END; DO HPOS = 0 TO 49; CALL WRITE$WORD( H( HPOS ) ); END; CALL WRITE$NL(); DO HPOS = 0 TO MAX$HUMBLE - 1; M = H( HPOS ); IF M < 10 THEN H1 = H1 + 1; ELSE IF M < 100 THEN H2 = H2 + 1; ELSE IF M < 1000 THEN H3 = H3 + 1; ELSE IF M < 10000 THEN H4 = H4 + 1; END; CALL WRITEHSTAT( H1, 1 ); CALL WRITEHSTAT( H2, 2 ); CALL WRITEHSTAT( H3, 3 ); CALL WRITEHSTAT( H4, 4 ); END MAIN;
END HUMBLE;</lang>
- Output:
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 there are 9 Humble numbers with 1 digit there are 36 Humble numbers with 2 digits there are 95 Humble numbers with 3 digits there are 197 Humble numbers with 4 digits
Python
<lang python>Humble numbers
from itertools import groupby, islice from functools import reduce
- humbles :: () -> [Int]
def humbles():
A non-finite stream of Humble numbers. OEIS A002473 hs = set([1]) while True: nxt = min(hs) yield nxt hs.remove(nxt) hs.update(nxt * x for x in [2, 3, 5, 7])
- TEST ----------------------------------------------------
- main :: IO ()
def main():
First 50, and counts with N digits
print('First 50 Humble numbers:\n') for row in chunksOf(10)( take(50)(humbles()) ): print(' '.join(map( lambda x: str(x).rjust(3), row )))
print('\nCounts of Humble numbers with n digits:\n') for tpl in take(10)( (k, len(list(g))) for k, g in groupby(len(str(x)) for x in humbles()) ): print(tpl)
- GENERIC -------------------------------------------------
- chunksOf :: Int -> [a] -> a
def chunksOf(n):
A series of lists of length n, subdividing the contents of xs. Where the length of xs is not evenly divible, the final list will be shorter than n. return lambda xs: reduce( lambda a, i: a + [xs[i:n + i]], range(0, len(xs), n), [] ) if 0 < n else []
- take :: Int -> [a] -> [a]
- take :: Int -> String -> String
def take(n):
The prefix of xs of length n, or xs itself if n > length xs. return lambda xs: ( list(islice(xs, n)) )
- MAIN ---
if __name__ == '__main__':
main()</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 Counts of Humble numbers with n digits: (1, 9) (2, 36) (3, 95) (4, 197) (5, 356) (6, 579) (7, 882) (8, 1272) (9, 1767) (10, 2381)
Racket
<lang racket>#lang racket
(define (gen-humble-numbers N (kons #f) (k0 (void)))
(define rv (make-vector N 1))
(define (loop n 2-idx 3-idx 5-idx 7-idx next-2 next-3 next-5 next-7 k) (if (= n N) rv (let ((mn (min next-2 next-3 next-5 next-7))) (vector-set! rv n mn) (define (add-1-if-min n x) (if (= mn n) (add1 x) x)) (define (*vr.i-if-min n m i) (if (= mn n) (* m (vector-ref rv i)) n)) (let* ((2-idx (add-1-if-min next-2 2-idx)) (next-2 (*vr.i-if-min next-2 2 2-idx)) (3-idx (add-1-if-min next-3 3-idx)) (next-3 (*vr.i-if-min next-3 3 3-idx)) (5-idx (add-1-if-min next-5 5-idx)) (next-5 (*vr.i-if-min next-5 5 5-idx)) (7-idx (add-1-if-min next-7 7-idx)) (next-7 (*vr.i-if-min next-7 7 7-idx)) (k (and kons (kons mn k)))) (loop (add1 n) 2-idx 3-idx 5-idx 7-idx next-2 next-3 next-5 next-7 k))))) (loop 1 0 0 0 0 2 3 5 7 (and kons (kons 1 k0))))
(define ((digit-tracker breaker) h last-ten.count)
(let ((last-ten (car last-ten.count))) (if (< h last-ten) (cons last-ten (add1 (cdr last-ten.count))) (begin (printf "~a humble numbers with ~a digits~%" (cdr last-ten.count) (order-of-magnitude last-ten)) (cons (breaker (* 10 last-ten)) 1)))))
(define (Humble-numbers)
(displayln (gen-humble-numbers 50)) (time (let/ec break (void (gen-humble-numbers 100000000 (digit-tracker (λ (o) (if (> (order-of-magnitude o) 100) (break) o))) '(10 . 0))))))
(module+ main
(Humble-numbers))
</lang>
- Output:
output has been elided manually, to avoid repetition with the numbers you've already seen elsewhere:
#(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 humble numbers with 1 digits 36 humble numbers with 2 digits 95 humble numbers with 3 digits 197 humble numbers with 4 digits 356 humble numbers with 5 digits 579 humble numbers with 6 digits 882 humble numbers with 7 digits 1272 humble numbers with 8 digits 1767 humble numbers with 9 digits 2381 humble numbers with 10 digits ... 17323 humble numbers with 20 digits ... 56618 humble numbers with 30 digits ... 132054 humble numbers with 40 digits ... 255415 humble numbers with 50 digits ... 438492 humble numbers with 60 digits ... 693065 humble numbers with 70 digits ... 1030928 humble numbers with 80 digits ... 1463862 humble numbers with 90 digits ... 2003661 humble numbers with 100 digits cpu time: 234970 real time: 235489 gc time: 189187
Raku
(formerly Perl 6)
<lang perl6>sub smooth-numbers (*@list) {
cache my \Smooth := gather { my %i = (flat @list) Z=> (Smooth.iterator for ^@list); my %n = (flat @list) Z=> 1 xx *;
loop { take my $n := %n{*}.min;
for @list -> \k { %n{k} = %i{k}.pull-one * k if %n{k} == $n; } } }
}
my $humble := smooth-numbers(2,3,5,7);
put $humble[^50]; say ;
my $upto = 50; my $digits = 1; my $count;
$humble.map: -> \h {
++$count and next if h.chars == $digits; printf "Digits: %2d - Count: %s\n", $digits++, $count; $count = 1; last if $digits > $upto;
}</lang>
- Output:
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 Digits: 1 - Count: 9 Digits: 2 - Count: 36 Digits: 3 - Count: 95 Digits: 4 - Count: 197 Digits: 5 - Count: 356 Digits: 6 - Count: 579 Digits: 7 - Count: 882 Digits: 8 - Count: 1272 Digits: 9 - Count: 1767 Digits: 10 - Count: 2381 Digits: 11 - Count: 3113 Digits: 12 - Count: 3984 Digits: 13 - Count: 5002 Digits: 14 - Count: 6187 Digits: 15 - Count: 7545 Digits: 16 - Count: 9081 Digits: 17 - Count: 10815 Digits: 18 - Count: 12759 Digits: 19 - Count: 14927 Digits: 20 - Count: 17323 Digits: 21 - Count: 19960 Digits: 22 - Count: 22853 Digits: 23 - Count: 26015 Digits: 24 - Count: 29458 Digits: 25 - Count: 33188 Digits: 26 - Count: 37222 Digits: 27 - Count: 41568 Digits: 28 - Count: 46245 Digits: 29 - Count: 51254 Digits: 30 - Count: 56618 Digits: 31 - Count: 62338 Digits: 32 - Count: 68437 Digits: 33 - Count: 74917 Digits: 34 - Count: 81793 Digits: 35 - Count: 89083 Digits: 36 - Count: 96786 Digits: 37 - Count: 104926 Digits: 38 - Count: 113511 Digits: 39 - Count: 122546 Digits: 40 - Count: 132054 Digits: 41 - Count: 142038 Digits: 42 - Count: 152515 Digits: 43 - Count: 163497 Digits: 44 - Count: 174986 Digits: 45 - Count: 187004 Digits: 46 - Count: 199565 Digits: 47 - Count: 212675 Digits: 48 - Count: 226346 Digits: 49 - Count: 240590 Digits: 50 - Count: 255415
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)──┘ */
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:
(Shown at 7/8 size.)
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
Ruby
Brute force and slow
Checks if each number upto limit is humble number.
<lang ruby>def humble?(i)
while i % 2 == 0; i /= 2 end while i % 3 == 0; i /= 3 end while i % 5 == 0; i /= 5 end while i % 7 == 0; i /= 7 end i == 1
end
count, num = 0, 0 digits = 10 # max digits for humble numbers limit = 10 ** digits # max numbers to search through humble = Array.new(digits + 1, 0)
while (num += 1) < limit
if humble?(num) humble[num.to_s.size] += 1 print num, " " if count < 50 count += 1 end
end
print "\n\nOf the first #{count} humble numbers:\n" (1..digits).each { |num| printf("%5d have %2d digits\n", humble[num], num) }</lang>
- Output:
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 7574 humble numbers: 9 have 1 digits 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 1767 have 9 digits 2381 have 10 digits
Direct Generation: Orders of magnitude faster
Generate humble numbers directly.
<lang ruby>def humble(digits)
h = [1] x2, x3, x5, x7 = 2, 3, 5, 7 i, j, k, l = 0, 0, 0, 0 n = 0 while n += 1 # ruby => 2.6: (1..).each do |n| x = [x2, x3, x5, x7].min break if x.to_s.size > digits h[n] = x x2 = 2 * h[i += 1] if x2 == h[n] x3 = 3 * h[j += 1] if x3 == h[n] x5 = 5 * h[k += 1] if x5 == h[n] x7 = 7 * h[l += 1] if x7 == h[n] end h
end
digits = 50 # max digits for humble numbers h = humble(digits) # humble numbers <= digits size count = h.size # the total humble numbers count
- counts = h.map { |n| n.to_s.size }.tally # hash of digits counts 1..digits: Ruby => 2.7
counts = h.map { |n| n.to_s.size }.group_by(&:itself).transform_values(&:size) # Ruby => 2.4 print "First 50 Humble Numbers: \n"; (0...50).each { |i| print "#{h[i]} " } print "\n\nOf the first #{count} humble numbers:\n" (1..digits).each { |num| printf("%6d have %2d digits\n", counts[num], num) }</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 Of the first 3363713 humble numbers: 9 have 1 digits 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 1767 have 9 digits 2381 have 10 digits 3113 have 11 digits 3984 have 12 digits 5002 have 13 digits 6187 have 14 digits 7545 have 15 digits 9081 have 16 digits 10815 have 17 digits 12759 have 18 digits 14927 have 19 digits 17323 have 20 digits 19960 have 21 digits 22853 have 22 digits 26015 have 23 digits 29458 have 24 digits 33188 have 25 digits 37222 have 26 digits 41568 have 27 digits 46245 have 28 digits 51254 have 29 digits 56618 have 30 digits 62338 have 31 digits 68437 have 32 digits 74917 have 33 digits 81793 have 34 digits 89083 have 35 digits 96786 have 36 digits 104926 have 37 digits 113511 have 38 digits 122546 have 39 digits 132054 have 40 digits 142038 have 41 digits 152515 have 42 digits 163497 have 43 digits 174986 have 44 digits 187004 have 45 digits 199565 have 46 digits 212675 have 47 digits 226346 have 48 digits 240590 have 49 digits 255415 have 50 digits
Sidef
<lang ruby>func smooth_generator(primes) {
var s = primes.len.of { [1] }
{ var n = s.map { .first }.min { |i| s[i].shift if (s[i][0] == n) s[i] << (n * primes[i]) } * primes.len n }
}
with (smooth_generator([2,3,5,7])) {|g|
say 50.of { g.run }.join(' ')
}
say "\nThe digit counts of humble numbers" say '═'*35
with (smooth_generator([2,3,5,7])) {|g|
for (var(d=1,c=0); d <= 20; ++c) { var n = g.run n.len > d || next say "#{'%10s'%c.commify} have #{'%2d'%d} digit#{[:s,][d==1]}" (c, d) = (0, n.len) }
}</lang>
- Output:
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
Visual Basic .NET
<lang vbnet>Module Module1
Function IsHumble(i As Long) As Boolean If i <= 1 Then Return True End If If i Mod 2 = 0 Then Return IsHumble(i \ 2) End If If i Mod 3 = 0 Then Return IsHumble(i \ 3) End If If i Mod 5 = 0 Then Return IsHumble(i \ 5) End If If i Mod 7 = 0 Then Return IsHumble(i \ 7) End If Return False End Function
Sub Main() Dim LIMIT = Short.MaxValue Dim humble As New Dictionary(Of Integer, Integer) Dim count = 0L Dim num = 1L
While count < LIMIT If (IsHumble(num)) Then Dim str = num.ToString Dim len = str.Length If len > 10 Then Exit While End If If humble.ContainsKey(len) Then humble(len) += 1 Else humble(len) = 1 End If If count < 50 Then Console.Write("{0} ", num) End If count += 1 End If num += 1 End While Console.WriteLine(vbNewLine)
Console.WriteLine("Of the first {0} humble numbers:", count) num = 1 While num < humble.Count If humble.ContainsKey(num) Then Dim c = humble(num) Console.WriteLine("{0,5} have {1,2} digits", c, num) num += 1 Else Exit While End If End While End Sub
End Module</lang>
- Output:
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 7574 humble numbers: 9 have 1 digits 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 1767 have 9 digits
Wren
Wren doesn't have arbitrary precision arithmetic and 'safe' integer operations are limited to a maximum absolute value of 2^53-1 (a 16 digit number). So there is no point in trying to generate humble numbers beyond that. <lang ecmascript>import "/fmt" for Fmt import "/math" for Int, Nums import "/sort" for Find
var humble = Fn.new { |n|
var h = List.filled(n, 0) h[0] = 1 var next2 = 2 var next3 = 3 var next5 = 5 var next7 = 7 var i = 0 var j = 0 var k = 0 var l = 0 for (m in 1...n) { h[m] = Nums.min([next2, next3, next5, next7]) if (h[m] == next2) { i = i + 1 next2 = 2 * h[i] } if (h[m] == next3) { j = j + 1 next3 = 3 * h[j] } if (h[m] == next5) { k = k + 1 next5 = 5 * h[k] } if (h[m] == next7) { l = l + 1 next7 = 7 * h[l] } } return h
}
var n = 43000 // say var h = humble.call(n) System.print("The first 50 humble numbers are:") System.print(h[0..49])
var f = Find.all(h, Int.maxSafe) // binary search var maxUsed = f[0] ? f[2].min + 1 : f[2].min var maxDigits = 16 // Int.maxSafe (2^53 -1) has 16 digits var counts = List.filled(maxDigits + 1, 0) var digits = 1 var pow10 = 10 for (i in 0...maxUsed) {
while (true) { if (h[i] >= pow10) { pow10 = pow10 * 10 digits = digits + 1 } else break } counts[digits] = counts[digits] + 1
} System.print("\nOf the first %(Fmt.dc(0, maxUsed)) humble numbers:") for (i in 1..maxDigits) {
var s = (i != 1) ? "s" : "" System.print("%(Fmt.dc(9, counts[i])) have %(Fmt.d(2, i)) digit%(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 42,037 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 8,632 have 16 digits
zkl
GNU Multiple Precision Arithmetic Library
<lang zkl>var [const] BI=Import("zklBigNum"); // libGMP var one = BI(1), two = BI(2), three = BI(3),
five = BI(5), seven = BI(7);
fcn humble(n){ // --> List of BigInt Humble numbers
h:=List.createLong(n); h.append(one); next2,next3 := two.copy(), three.copy(); next5,next7 := five.copy(), seven.copy(); reg i=0,j=0,k=0,l=0; do(n-1){ h.append( hm:=BI(next2.min(next3.min(next5.min(next7)))) ); if(hm==next2) next2.set(two) .mul(h[i+=1]); if(hm==next3) next3.set(three).mul(h[j+=1]); if(hm==next5) next5.set(five) .mul(h[k+=1]); if(hm==next7) next7.set(seven).mul(h[l+=1]); } h
}</lang> <lang zkl>fcn __main__{
const N = 5 * 1e6; // calculate the first 1 million humble numbers, say h:=humble(N); println("The first 50 humble numbers are:\n ",h[0,50].concat(" ")); counts:=Dictionary(); // tally the number of digits in each number h.apply2('wrap(n){ counts.incV(n.numDigits) });
println("\nOf the first %,d humble numbers:".fmt(h.len())); println("Digits Count"); foreach n in (counts.keys.apply("toInt").sort()){ println("%2d %,9d".fmt(n,counts[n], n)); }
}</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 5,000,000 humble numbers: Digits Count 1 9 2 36 3 95 4 197 5 356 6 579 7 882 8 1,272 9 1,767 10 2,381 11 3,113 12 3,984 13 5,002 14 6,187 15 7,545 16 9,081 17 10,815 18 12,759 19 14,927 20 17,323 21 19,960 22 22,853 23 26,015 24 29,458 25 33,188 26 37,222 27 41,568 28 46,245 29 51,254 30 56,618 31 62,338 32 68,437 33 74,917 34 81,793 35 89,083 36 96,786 37 104,926 38 113,511 39 122,546 40 132,054 41 142,038 42 152,515 43 163,497 44 174,986 45 187,004 46 199,565 47 212,675 48 226,346 49 240,590 50 255,415 51 270,843 52 286,880 53 303,533 54 320,821 55 338,750 56 115,460