Humble numbers: Difference between revisions
→{{header|C sharp|C#}}: added direct generatio logarithms version
m (→{{header|REXX}}: used a smaller font for the output section.) |
(→{{header|C sharp|C#}}: added direct generatio logarithms version) |
||
Line 596:
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</pre>
=== 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>
{{out}}
verified results against the Pascal entry:
<pre style="height:64ex;overflow:scroll">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</pre>
=={{header|C++}}==
| |||