Humble numbers: Difference between revisions

{{trans|C++}}

 

I i <= 1

R 1B

I num !C humble

L.break

 

{{out}}

 

=={{header|Ada}}==

 

procedure Show_Humble is

Count_Humble_Digits;

Show_Digit_Counts;

 

{{out}}

 

=={{header|ALGOL 68}}==

INT max humble = 2048;

INT max shown humble = 49;

)

OD

{{out}}

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

 

=={{header|AutoHotkey}}==

while (c < 50)

{

ans.push(n)

return ans

{{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|AWK}}==

# syntax: GAWK -f HUMBLE_NUMBERS.AWK

#

return(0)

}

{{out}}

<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

=== Direct Generation - Variant ===

A direct generation variant. Rather quick, as the humble numbers are not generated in order. And the digits are not counted individually, the log representation of each humble number is just binned into the decade tally with a simple division by log(10). Note: g++ compiler options: <code>-O3 -std=c++17</code>

#include <cmath>

#include <locale>

delete [] bins;

printf("Counting took %8f seconds\n", duration<double>(steady_clock::now() - st).count());

{{out}}

Seems to give correct values as compared to the pascal (modification of hamming numbers fast alternative) version. And goes noticeably faster, up to 877 digits in about 3 1/4 minutes, where as pascal takes 1 1/3 hours to get to 877 digits.

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

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

</pre>

=={{header|Factor}}==

generalizations io kernel make math math.functions math.order

prettyprint sequences tools.memory.private ;

] tri ] time ;

 

{{out}}

<pre style="height:45ex">

=={{header|FreeBASIC}}==

{{trans|Visual Basic .NET}}

If i <= 1 Then Return True

If i Mod 2 = 0 Then Return IsHumble(i \ 2)

Exit While

End If

{{out}}

<pre>Los 50 primeros números de Humble son:

=={{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:

=={{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:

===Brute force===

First, brute force (because we can) ...

# Input: a positive integer

# Output: true iff the input is humble

(.humble | range(1;length) as $i | " \($i): \(.[$i])") ;

 

{{out}}

<pre>First 50:

 

Having already shown one way to display the first few humble numbers, this subsection will focus on the more difficult problem.

# A generator

def humbles($digits):

(distribution(humbles($digits)) | range(0;length) as $i | " \($i+1): \(.[$i])") ;

 

{{out}}

<pre>Distribution of the number of decimal digits up to 16 digits:

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

Create a simple function which efficiently generates humble numbers up to an inputted max number, then call it twice to generate the output. Finds the number of humble numbers with digits up to 100 in 5 minutes.

 

Sort[Flatten@ParallelTable[

2^i 3^j 5^k 7^m, {i, 0, Log[2, max]}, {j, 0, Log[3, max/2^i]}, {k,

"\nDigits\[Rule]Count",

Rule @@@ Tally[IntegerLength /@ Drop[HumbleGenerator[10^100], -1]] //

 

{{out}}

=={{header|Nim}}==

A simple algorithm efficient enough to get the number of humble numbers with 18 digits in less than four seconds. To get further, we would have to use big numbers and a more efficient algorithm.

 

 

echo ""

echo "Count of humble numbers with n digits:"

 

{{out}}

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.

<span style="color: #000080;font-style:italic;">-- demo/rosetta/humble.exw</span>

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #000000;">humble</span><span style="color: #0000FF;">(</span><span style="color: #000000;">50</span><span style="color: #0000FF;">)</span>

<span style="color: #000000;">humble</span><span style="color: #0000FF;">(</span><span style="color: #000000;">42</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">)</span>

{{out}}

<pre>

{{Trans|ALGOL W}}This can be compiled with the original 8080 PL/M compiler and run under CP/M or an emulator or clone.

Only handles Humble numbers with up to 4 digits as 8080 PL/M only has unsigned 8 and 16 bit integers.

BDOS: PROCEDURE( FN, ARG ); /* CP/M BDOS SYSTEM CALL */

DECLARE FN BYTE, ARG ADDRESS;

CALL PRINT$H$STAT( H3, 3 );

CALL PRINT$H$STAT( H4, 4 );

{{out}}

<pre>

Note the use of text in column 81 onwards to hide the PL/I specifics from the PL/M compiler.<br><br>

Based on the PL/M version, note PL/I does not have the "walrus operator" (:=) which allows assignments to be nested in expressions, so it can't be used in the non-PL/M specific parts of this.

humble_100H: procedure options (main);

 

CALL PRHUMBLESTAT( H4, 4 );

 

{{out}}

<pre>

=={{header|Python}}==

{{Works with|Python|3.7}}

 

from itertools import groupby, islice

# MAIN ---

if __name__ == '__main__':

{{Out}}

<pre>First 50 Humble numbers:

Uses <code>smoothwith</code> from [[N-smooth numbers#Quackery]], and <code>searchwith</code> from [[Binary search#Quackery]].

 

[ -1 peek [ 10 12 ** ] constant = ]

-1 split drop

say "-digit humble numbers" cr ]

drop

 

{{out}}

{{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:}}

 

=={{header|Ring}}==

{{Improve|Ring|Makes zero attempt at the second part of the task}}

load "stdlib.ring"

 

see "" + numList[n] + " "

next

Output:

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

 

=={{header|Tcl}}==

proc humble? x {

foreach f {2 3 5 7} {

}

puts $t1

Task 1:

{{out}}

 

Task 2, took a long while due to brute force:

proc task2 {nmax} {

puts "Distribution of digit length for the first $nmax humble numbers"

}

task2 4096

{{out}}

<pre>~ $ time ./humble.tcl

=={{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-sort}}

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.

import "/math" for Int, Nums

import "/sort" for Find

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

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

 

{{out}}

{{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">