Humble numbers: Difference between revisions

{{task|Prime Numbers}}

 

 

 

 

;References:

:*   [http://www.informatik.uni-ulm.de/acm/Locals/1996/number.sol University of Ulm, The first 5842 terms of humble numbers]

<br><br>

{{trans|C++}}

 

I i <= 1

R 1B

I num !C humble

L.break

 

{{out}}

1272 have 8 digits

1767 have 9 digits

</pre>

 

=={{header|Ada}}==

 

procedure Show_Humble is

Count_Humble_Digits;

Show_Digit_Counts;

 

{{out}}

8 1272

9 1767</pre>

 

=={{header|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.

% returns the minimum of a and b %

integer procedure min ( integer value a, b ) ; if a < b then a else b;

write( "there are", h6, " Humble numbers with 6 digits" )

end

{{out}}

<pre>

there are 579 Humble numbers with 6 digits

</pre>

=={{header|AWK}}==

# syntax: GAWK -f HUMBLE_NUMBERS.AWK

#

return(0)

}

{{out}}

<pre>

1767 9

</pre>

 

=={{header|C}}==

{{trans|C++}}

#include <stdbool.h>

#include <stdio.h>

 

return 0;

{{out}}

<pre>1 2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27 28 30 32 35 36 40 42 45 48 49 50 54 56 60 63 64 70 72 75 80 81 84 90 96 98 100 105 108 112 120

=={{header|C sharp|C#}}==

{{trans|D}}

using System.Collections.Generic;

 

}

}

{{out}}

<pre>1 2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27 28 30 32 35 36 40 42 45 48 49 50 54 56 60 63 64 70 72 75 80 81 84 90 96 98 100 105 108 112 120

{{trans|Go}}

{{libheader|System.Numerics}}

 

using System;

Console.WriteLine("The first {0} humble numbers are: {1}", firstAmt, string.Join(" ",h.Take(firstAmt)));

}

{{out}}

Results from a core i7-7700 @ 3.6Ghz.<br/>BigIntegers: (tabulates up to 100 digits in about 3/4 of a minute, but a lot of memory is consumed - 4.2 GB)

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.

 

using UI = System.UInt64;

 

humLog(255); // see tabulation for digits 1 to 255

}

{{out}}

verified results against the Pascal entry:

=={{header|C++}}==

{{trans|Kotlin}}

#include <iostream>

#include <map>

 

return 0;

{{out}}

<pre>1 2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27 28 30 32 35 36 40 42 45 48 49 50 54 56 60 63 64 70 72 75 80 81 84 90 96 98 100 105 108 112 120

1272 have 8 digits

1767 have 9 digits</pre>

 

=={{header|Crystal}}==

Checks if each number upto limit is humble number.

{{trans|C++}}

return true if (i < 2)

return humble?(i // 2) if (i % 2 == 0)

 

print "\n\nOf the first #{count} humble numbers:\n"

{{out}}

<pre>1 2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27 28 30 32 35 36 40 42 45 48 49 50 54 56 60 63 64 70 72 75 80 81 84 90 96 98 100 105 108 112 120

Generate humble numbers directly.

{{trans|Zkl}}

 

def humble(digits)

print "First 50 Humble Numbers: \n"; (0...50).each { |i| print "#{h[i]} " }

print "\n\nOf the first #{count} humble numbers:\n"

{{out}}

<pre>First 50 Humble Numbers:

=={{header|D}}==

{{trans|C++}}

import std.stdio;

 

}

}

{{out}}

<pre>1 2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27 28 30 32 35 36 40 42 45 48 49 50 54 56 60 63 64 70 72 75 80 81 84 90 96 98 100 105 108 112 120

1272 have 8 digits

1767 have 9 digits</pre>

 

=={{header|F_Sharp|F#}}==

===The Functions===

// Generate humble numbers. Nigel Galloway: June 18th., 2020

let fN g=let mutable n=1UL in (fun()->n<-n*g;n)

|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))))}

===The Tasks===

humble |> Seq.take 50 |> Seq.iter (printf "%d ");printfn ""

{{out}}

<pre>

1 2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27 28 30 32 35 36 40 42 45 48 49 50 54 56 60 63 64 70 72 75 80 81 84 90 96 98 100 105 108 112 120

</pre>

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

{{out}}

<pre>

There are 12759 humble numbers with 18 digits

</pre>

=={{header|Factor}}==

generalizations io kernel make math math.functions math.order

prettyprint sequences tools.memory.private ;

] tri ] time ;

 

{{out}}

<pre style="height:45ex">

Running time: 335.1803624581294 seconds

</pre>

 

=={{header|Go}}==

Not particularly fast and uses a lot of memory but easier to understand than the 'log' based methods for generating 7-smooth numbers.

 

import (

fmt.Printf("%9s have %2d digit%s\n", commatize(counts[i]), i, s)

}

 

{{out}}

 

=={{header|Haskell}}==

import Data.List.Split (chunksOf)

import Data.List (group)

------------------------- DISPLAY -------------------------

justifyRight :: Int -> a -> [a] -> [a]

{{Out}}

<pre>First 50 Humble numbers:

(24,29458)

(25,33188)</pre>

 

=={{header|J}}==

Multiply all the humble numbers by all the factors appending the next largest value.

humble=: 4 : 0

NB. x humble y generates x humble numbers based on factors y

end.

)

<pre>

p: i.4

 

Use a class to simulate the python generator. This is a more efficient implementation of the first method.

FACTORS_h_=: p: i. 4

HUMBLE_h_=: 1

)

reset_h_=: 3 :'0 $ HUMBLE=: 1'

<pre>

3 :0 [ 50 [ reset_h_''

 

=={{header|Java}}==

import java.math.BigInteger;

import java.util.ArrayList;

 

}

{{Out}}

<pre>

 

=={{header|JavaScript}}==

'use strict';

 

// MAIN ---

return main();

{{Out}}

<pre>First 50 humble numbers:

9 -> 1767

10 -> 2381</pre>

 

=={{header|Julia}}==

To spare heap memory, keeps only the last 2 million values found for use in the generation of further values.

function counthumbledigits(maxdigits, returnsequencelength=50)

n, count, adjustindex, maxdiff = BigInt(1), 0, BigInt(0), 0

println(lpad(digitcounts[ndigits], 10), " have ", lpad(ndigits, 3), " digits.")

end

<pre>

828.693164 seconds (3.61 G allocations: 64.351 GiB, 51.37% gc time)

 

=={{header|Kotlin}}==

if (i <= 1) return true

if (i % 2 == 0) return isHumble(i / 2)

}

}

{{out}}

<pre>1 2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27 28 30 32 35 36 40 42 45 48 49 50 54 56 60 63 64 70 72 75 80 81 84 90 96 98 100 105 108 112 120

=={{header|Lua}}==

{{trans|C}}

local n2 = math.floor(n)

 

end

 

{{out}}

<pre>1 2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27 28 30 32 35 36 40 42 45 48 49 50 54 56 60 63 64 70 72 75 80 81 84 90 96 98 100 105 108 112 120

1272 have 8 digits

1767 have 9 digits</pre>

 

=={{header|Pascal}}==

float32 get wrong at 37 digits,->37 104925 instead of 104926<BR>

runtime: 2 x digits => ~ runtime 2^4 <BR>

{$IFDEF FPC}

{$MODE DELPHI}

first50;

GetDigitCounts(100);

{{out}}

<pre>1 2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27 28 30 32 35 36 40 42 45 48 49 50 54 56 60 63 64 70 72 75 80 81 84 90 96 98 100 105 108 112 120

 

=={{header|Perl}}==

use warnings;

use List::Util 'min';

printf "Digits: %2d - Count: %s\n", $digits++, $count;

$count = 1;

{{out}}

<pre style="height:20ex">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

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)<br>

I also tried a log version (similar to [[Hamming_numbers#A_much_faster_logarithmic_version|Hamming_numbers]]) but inaccuracies with floor(h[n][LOG]) crept in quite early, at just 10 digits.

{{out}}

<pre>

152,515 humble numbers have 42 digits (23.9s, total:1,703,635)

</pre>

 

=={{header|PL/M}}==

{{out}}

<pre>

</pre>

 

=={{header|Python}}==

{{Works with|Python|3.7}}

 

from itertools import groupby, islice

# MAIN ---

if __name__ == '__main__':

{{Out}}

<pre>First 50 Humble numbers:

(9, 1767)

(10, 2381)</pre>

 

=={{header|Racket}}==

{{trans|Go}}

 

 

(define (gen-humble-numbers N (kons #f) (k0 (void)))

(module+ main

(Humble-numbers))

 

{{out}}

{{works with|Rakudo|2019.07.1}}

 

cache my \Smooth := gather {

my %i = (flat @list) Z=> (Smooth.iterator for ^@list);

$count = 1;

last if $digits > $upto;

{{out}}

<pre>1 2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27 28 30 32 35 36 40 42 45 48 49 50 54 56 60 63 64 70 72 75 80 81 84 90 96 98 100 105 108 112 120

 

=={{header|REXX}}==

parse arg n m . /*obtain optional arguments from the CL*/

if n=='' | n=="," then n= 50 /*Not specified? Then use the default.*/

$.L= $.L + 1 /*bump the digit count for this number.*/

end /*h*/ /*the humble numbers are in the @ array*/

{{out|output|text=&nbsp; when using the default inputs:}}

 

 

total number of humble numbers found: 6,870,667

</pre>

 

Checks if each number upto limit is humble number.

{{trans|Crystal}}

while i % 2 == 0; i /= 2 end

while i % 3 == 0; i /= 3 end

 

print "\n\nOf the first #{count} humble numbers:\n"

{{out}}

<pre>1 2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27 28 30 32 35 36 40 42 45 48 49 50 54 56 60 63 64 70 72 75 80 81 84 90 96 98 100 105 108 112 120

Generate humble numbers directly.

{{trans|Zkl}}

h = [1]

x2, x3, x5, x7 = 2, 3, 5, 7

print "First 50 Humble Numbers: \n"; (0...50).each { |i| print "#{h[i]} " }

print "\n\nOf the first #{count} humble numbers:\n"

{{out}}

<pre>First 50 Humble Numbers:

 

=={{header|Sidef}}==

 

var s = primes.len.of { [1] }

(c, d) = (0, n.len)

}

{{out}}

<pre>

14,927 have 19 digits

17,323 have 20 digits

</pre>

 

=={{header|Visual Basic .NET}}==

{{trans|C#}}

 

Function IsHumble(i As Long) As Boolean

End Sub

 

{{out}}

<pre>1 2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27 28 30 32 35 36 40 42 45 48 49 50 54 56 60 63 64 70 72 75 80 81 84 90 96 98 100 105 108 112 120

{{libheader|Wren-math}}

{{libheader|Wren-sort}}

 

var humble = Fn.new { |n|

System.print(h[0..49])

 

var maxUsed = f[0] ? f[2].min + 1 : f[2].min

var counts = List.filled(maxDigits + 1, 0)

var digits = 1

var s = (i != 1) ? "s" : ""

System.print("%(Fmt.dc(9, counts[i])) have %(Fmt.d(2, i)) digit%(s)")

 

{{out}}

7,545 have 15 digits

8,632 have 16 digits

</pre>

 

{{trans|Go}}

{{libheader|GMP}} GNU Multiple Precision Arithmetic Library

var one = BI(1), two = BI(2), three = BI(3),

five = BI(5), seven = BI(7);

}

h

const N = 5 * 1e6; // calculate the first 1 million humble numbers, say

h:=humble(N);

println("%2d %,9d".fmt(n,counts[n], n));

}

{{out}}

<pre style="height:45ex">