Increasing gaps between consecutive Niven numbers

From Rosetta Code
Increasing gaps between consecutive Niven numbers is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Note:   Niven   numbers are also called   Harshad   numbers.

  They are also called   multidigital   numbers.


Niven numbers are positive integers which are evenly divisible by the sum of its digits   (expressed in base ten).

Evenly divisible   means   divisible with no remainder.


Task
  •   find the gap (difference) of a Niven number from the previous Niven number
  •   if the gap is   larger   than the (highest) previous gap,   then:
  •   show the index (occurrence) of the gap     (the 1st gap is 1)
  •   show the index of the Niven number that starts the gap     (1st Niven number is 1,   33rd Niven number is 100)
  •   show the Niven number that starts the gap
  •   show all numbers with comma separators where appropriate   (optional)
  •   I.E.:   the gap size of   60   starts at the   33,494th   Niven number which is Niven number   297,864
  •   show all increasing gaps up to the   ten millionth   (10,000,000th)   Niven number
  •   (optional)   show all gaps up to whatever limit is feasible/practical/realistic/reasonable/sensible/viable on your computer
  •   show all output here, on this page


Related task


Also see



Go[edit]

This reuses code from the [Harshad or Niven series] task though converted to use 'uint64' rather than 'int' in case anyone is running Go on a 32-bit platform.

package main
 
import "fmt"
 
type is func() uint64
 
func newSum() is {
var ms is
ms = func() uint64 {
ms = newSum()
return ms()
}
var msd, d uint64
return func() uint64 {
if d < 9 {
d++
} else {
d = 0
msd = ms()
}
return msd + d
}
}
 
func newHarshard() is {
i := uint64(0)
sum := newSum()
return func() uint64 {
for i++; i%sum() != 0; i++ {
}
return i
}
}
 
func commatize(n uint64) 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() {
fmt.Println("Gap Index of gap Starting Niven")
fmt.Println("=== ============= ==============")
h := newHarshard()
pg := uint64(0) // previous highest gap
pn := h() // previous Niven number
for i, n := uint64(1), h(); n <= 20e9; i, n = i+1, h() {
g := n - pn
if g > pg {
fmt.Printf("%3d  %13s  %14s\n", g, commatize(i), commatize(pn))
pg = g
}
pn = n
}
}
Output:
Gap    Index of gap   Starting Niven
===   =============   ==============
  1               1                1
  2              10               10
  6              11               12
  7              26               63
  8              28               72
 10              32               90
 12              83              288
 14             102              378
 18             143              558
 23             561            2,889
 32             716            3,784
 36           1,118            6,480
 44           2,948           19,872
 45           4,194           28,971
 54           5,439           38,772
 60          33,494          297,864
 66          51,544          478,764
 72          61,588          589,860
 88          94,748          989,867
 90         265,336        2,879,865
 99         800,054        9,898,956
108       3,750,017       49,989,744
126       6,292,149       88,996,914
135      44,194,186      689,988,915
144      55,065,654      879,987,906
150      61,074,615      989,888,823
153     179,838,772    2,998,895,823
192     399,977,785    6,998,899,824
201     497,993,710    8,889,999,624
234     502,602,764    8,988,988,866
258     547,594,831    9,879,997,824
276   1,039,028,518   18,879,988,824


Julia[edit]

using Formatting
 
function findharshadgaps(N)
isharshad(i) = i % sum(digits(i)) == 0
println("Gap Index Number Index Niven Number")
lastnum, lastnumidx, biggestgap = 1, 1, 0
for i in 2:N
if isharshad(i)
if (gap = i - lastnum) > biggestgap
println(lpad(gap, 5), lpad(format(lastnumidx, commas=true), 14),
lpad(format(lastnum, commas=true), 18))
biggestgap = gap
end
lastnum, lastnumidx = i, lastnumidx + 1
end
end
end
 
findharshadgaps(50_000_000_000)
 
Output:
Gap Index  Number Index  Niven Number
    1             1                 1
    2            10                10
    6            11                12
    7            26                63
    8            28                72
   10            32                90
   12            83               288
   14           102               378
   18           143               558
   23           561             2,889
   32           716             3,784
   36         1,118             6,480
   44         2,948            19,872
   45         4,194            28,971
   54         5,439            38,772
   60        33,494           297,864
   66        51,544           478,764
   72        61,588           589,860
   88        94,748           989,867
   90       265,336         2,879,865
   99       800,054         9,898,956
  108     3,750,017        49,989,744
  126     6,292,149        88,996,914
  135    44,194,186       689,988,915
  144    55,065,654       879,987,906
  150    61,074,615       989,888,823
  153   179,838,772     2,998,895,823
  192   399,977,785     6,998,899,824
  201   497,993,710     8,889,999,624
  234   502,602,764     8,988,988,866
  258   547,594,831     9,879,997,824
  276 1,039,028,518    18,879,988,824

Pascal[edit]

Works with: Free Pascal

As fast as GO

program NivenGaps;
{$IFDEF FPC}
{$MODE DELPHI}
{$OPTIMIZATION ON,ALL}
{$ELSE}
{$APPTYPE DELPHI}
{$ENDIF}
uses
sysutils,
strutils;
const
base = 10;
type
tNum = Uint64;
const
cntbasedigits = ((trunc(ln(High(tNum))/ln(base))+1) DIV 8 +1) *8;
type
tSumDigit = record
sdDigits : array[0..cntbasedigits-1] of byte;
sdNumber,
sdNivCount,
sdSumDig : tNum;
sdIsNiven : boolean;
end;
var
MySumDig : tSumDigit;
 
procedure OutNivenGap(ln,num,delta:TNum);
Begin
writeln(delta:3,Numb2USA(IntToStr(MySumDig.sdNivCount-1)):16,
Numb2USA(IntToStr(ln)):17);
end;
 
function InitSumDigit( n : tNum):tSumDigit;
var
sd : tSumDigit;
qt : tNum;
i : NativeInt;
begin
with sd do
begin
sdNumber:= n;
fillchar(sdDigits,SizeOf(sdDigits),#0);
sdSumDig :=0;
sdIsNiven := false;
i := 0;
// calculate Digits und sum them up
while n > 0 do
begin
qt := n div base;
{n mod base}
sdDigits[i] := n-qt*base;
inc(sdSumDig,sdDigits[i]);
n:= qt;
inc(i);
end;
IF sdSumDig >0 then
sdIsNiven := (sdNumber MOD sdSumDig = 0);
sdNivCount := Ord( sdIsNiven);
end;
InitSumDigit:=sd;
end;
 
procedure NextNiven(var sd:tSumDigit);
var
Num,Sum : tNum;
i,d,One: NativeUInt;
begin
One := 1;// put it in a register :-)
with sd do
begin
num := sdNumber;
Sum := sdSumDig;
repeat
//inc sum of digits
i := 0;
num += One;
repeat
d := sdDigits[i]+One;
Sum += One;
//base-1 times the repeat is left here
if d < base then
begin
sdDigits[i] := d;
BREAK;
end
else
begin
sdDigits[i] := 0;
i += One;
dec(Sum,base);
end;
until i > high( sdDigits);
until (Num MOD Sum) = 0;
sdIsNiven := true;
sdNumber := num;
sdSumDig := Sum;
inc(sdNivCount);
end;
end;
 
procedure FindGaps;
var
delta,LastNiven : TNum;
Begin
writeln('Gap Index of gap Starting Niven');
writeln('=== ============= ==============');
 
LastNiven:= 1;
MySumDig:=InitSumDigit(LastNiven);
delta := 0;
repeat
NextNiven(MySumDig);
with MySumDig do
Begin
IF delta < sdNumber-LastNiven then
begin
delta := sdNumber-LastNiven;
OutNivenGap(LastNiven,sdNumber,delta);
end;
LastNiven:= sdNumber;
end;
until MySumDig.sdNumber > 20*1000*1000*1000;
end;
 
begin
FindGaps;
end.
Output:
Gap    Index of gap   Starting Niven
===   =============   ==============
  1               1                1
  2              10               10
  6              11               12
  7              26               63
  8              28               72
 10              32               90
 12              83              288
 14             102              378
 18             143              558
 23             561            2,889
 32             716            3,784
 36           1,118            6,480
 44           2,948           19,872
 45           4,194           28,971
 54           5,439           38,772
 60          33,494          297,864
 66          51,544          478,764
 72          61,588          589,860
 88          94,748          989,867
 90         265,336        2,879,865
 99         800,054        9,898,956
108       3,750,017       49,989,744
126       6,292,149       88,996,914
135      44,194,186      689,988,915
144      55,065,654      879,987,906
150      61,074,615      989,888,823
153     179,838,772    2,998,895,823
192     399,977,785    6,998,899,824
201     497,993,710    8,889,999,624
234     502,602,764    8,988,988,866
258     547,594,831    9,879,997,824
276   1,039,028,518   18,879,988,824
real    2m37,350s


Limit = 1e12  hoped for 9,879,997,824 * 100  
used array of function 
function NumMod3(n:NativeUInt):NativeUInt;Begin result:=n-(n DIV 3)*3;end;
function NumMod4(n:NativeUInt):NativeUInt;Begin result:=n-(n DIV 4)*4;end;
..
function NumMod216(n:NativeUInt):NativeUInt;Begin result:=n-(n DIV 216)*216;end
..
assign the functions
FModN[1] := @NumMod1;
FModN[2] := @NumMod2;

leads to:
  repeat
    num += 1;
    sum:= NextSum(sum,@sd.sdDigits[0]);
  until FModN[Sum](Num) = 0;
//until (Num MOD Sum) = 0;// div is slow waiting for Intel Ice-Lake 18 cycles/64Bit instead of 97?


276   1,039,028,518   18,879,988,824
294  14,192,408,715  286,889,989,806
300  14,761,794,180  299,989,897,728
312  19,274,919,138  394,899,998,808
326  19,404,508,330  397,999,889,616
420  23,690,581,129  489,987,799,644
453  37,472,300,164  799,799,878,437

real    68m44,463s //15,26 cpu-cycles per number

Perl[edit]

Translation of: Perl 6
use strict;
use warnings;
use List::Util 'sum';
 
sub comma { reverse ((reverse shift) =~ s/(.{3})/$1,/gr) =~ s/^,//r }
 
my ($index, $last, $gap, $count) = (0, 0, 0, 0);
my $threshold = 10_000_000;
 
print "Gap Index of gap Starting Niven\n";
while (1) {
$count++;
next unless 0 == $count % sum split //, $count;
if ((my $diff = $count - $last) > $gap) {
$gap = $diff;
printf "%3d %15s %15s\n", $gap, $index > 1 ? comma $index : 1, $last > 1 ? comma $last : 1;
}
$last = $count;
last if ++$index >= $threshold;
}
Output:
Gap    Index of gap  Starting Niven
  1               1               1
  2              10              10
  6              11              12
  7              26              63
  8              28              72
 10              32              90
 12              83             288
 14             102             378
 18             143             558
 23             561           2,889
 32             716           3,784
 36           1,118           6,480
 44           2,948          19,872
 45           4,194          28,971
 54           5,439          38,772
 60          33,494         297,864
 66          51,544         478,764
 72          61,588         589,860
 88          94,748         989,867
 90         265,336       2,879,865
 99         800,054       9,898,956
108       3,750,017      49,989,744
126       6,292,149      88,996,914

Perl 6[edit]

Works with: Rakudo version 2019.11
use Lingua::EN::Numbers;
 
unit sub MAIN (Int $threshold = 10000000);
 
my int $index = 0;
my int $last = 0;
my int $gap = 0;
 
say 'Gap Index of gap Starting Niven';
 
for 1..* -> \count {
next unless count %% sum count.comb;
if (my \diff = count - $last) > $gap {
$gap = diff;
printf "%3d %15s %15s\n", $gap, comma($index || 1), comma($last || 1);
}
++$index;
$last = count;
last if $index >= $threshold;
}
Output:
Gap    Index of gap  Starting Niven
  1               1               1
  2              10              10
  6              11              12
  7              26              63
  8              28              72
 10              32              90
 12              83             288
 14             102             378
 18             143             558
 23             561           2,889
 32             716           3,784
 36           1,118           6,480
 44           2,948          19,872
 45           4,194          28,971
 54           5,439          38,772
 60          33,494         297,864
 66          51,544         478,764
 72          61,588         589,860
 88          94,748         989,867
 90         265,336       2,879,865
 99         800,054       9,898,956
108       3,750,017      49,989,744
126       6,292,149      88,996,914

Phix[edit]

Replaced sum(digits) in the original with sd, otherwise no great attempt to optimise

integer n = 1, prev = 1, g, gap = 0, count = 1, sd = 1
sequence digits={1}
 
procedure nNiven()
while 1 do
n += 1
for i=length(digits) to 0 by -1 do
if i=0 then
digits = prepend(digits,1)
exit
end if
if digits[i]<9 then
digits[i] += 1
exit
end if
digits[i] = 0
sd -= 9
end for
sd += 1
if remainder(n,sd)=0 then exit end if
end while
end procedure
 
printf(1,"gap size Niven index Niven #\n")
atom t0 = time()
while n<=1_000_000_000 do
nNiven()
g = n-prev
if g>gap then
string e = elapsed(time()-t0)
printf(1,"%,5d %,14d %,15d (%s)\n",{g, count, prev, e})
gap = g
end if
prev = n
count += 1
end while
Output:
gap size    Niven index      Niven #
    1              1               1 (0s)
    2             10              10 (0s)
    6             11              12 (0s)
    7             26              63 (0.0s)
    8             28              72 (0.0s)
   10             32              90 (0.0s)
   12             83             288 (0.0s)
   14            102             378 (0.0s)
   18            143             558 (0.0s)
   23            561           2,889 (0.0s)
   32            716           3,784 (0.0s)
   36          1,118           6,480 (0.0s)
   44          2,948          19,872 (0.0s)
   45          4,194          28,971 (0.0s)
   54          5,439          38,772 (0.0s)
   60         33,494         297,864 (0.0s)
   66         51,544         478,764 (0.0s)
   72         61,588         589,860 (0.0s)
   88         94,748         989,867 (0.1s)
   90        265,336       2,879,865 (0.1s)
   99        800,054       9,898,956 (0.4s)
  108      3,750,017      49,989,744 (1.7s)
  126      6,292,149      88,996,914 (3.0s)
  135     44,194,186     689,988,915 (22.9s)
  144     55,065,654     879,987,906 (29.1s)
  150     61,074,615     989,888,823 (32.7s)

REXX[edit]

/*REXX program finds and displays the largest gap between  Niven  numbers (up to LIMIT).*/
parse arg lim . /*obtain optional arguments from the CL*/
if lim=='' | lim==',' then lim= 10000000 /*Not specified? Then use the default.*/
numeric digits 2 + max(8, length(lim) ) /*enable the use of any sized numbers. */
gap= 0; old= 0 /*initialize (largest) gap; old Niven #*/
@gsa= 'gap starts at Niven #'
call tell center('gap size', 12) center(@gsa "index", 29) center(@gsa, 29)
call tell copies('═' , 12) copies('═' , 29) copies('═' , 29)
#= 0 /*#: is the index of a Niven number. */
do n=1 /*◄───── let's go Niven number hunting.*/
parse var n 1 sum 2 q /*use the first decimal digit for SUM.*/
do while q\==''; parse var q x 2 q; sum= sum + x
end /*while*/ /* ↑ */
if n//sum >0 then iterate /* └──────◄ is destructively parsed.*/
#= # + 1 /*bump the index of the Niven number.*/
if n-old<=gap then do; old= n; iterate; end /*Is gap not bigger? Then keep looking*/
gap= n - old; old= n /*We found a bigger gap; define new gap*/
idx= max(1, #-1); san= max(1, n-gap) /*handle special case of the first gap.*/
call tell right(commas(gap), 7)left('', 5), /*center right─justified Niven gap size*/
right(commas(idx), 25)left('', 4), /* " " " Niven num idx.*/
right(commas(san), 25) /* " " " " number. */
if n >= lim then leave /*have we exceeded the (huge) LIMit ? */
end /*n*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
commas: parse arg _; do c=length(_)-3 to 1 by -3; _=insert(',', _, c); end; return _
tell: say arg(1); return
output   when using the input of:     20000000000                 (which is   20   billion)
  gap size    gap starts at Niven # index      gap starts at Niven #
════════════ ═════════════════════════════ ═════════════════════════════
      1                              1                             1
      2                             10                            10
      6                             11                            12
      7                             26                            63
      8                             28                            72
     10                             32                            90
     12                             83                           288
     14                            102                           378
     18                            143                           558
     23                            561                         2,889
     32                            716                         3,784
     36                          1,118                         6,480
     44                          2,948                        19,872
     45                          4,194                        28,971
     54                          5,439                        38,772
     60                         33,494                       297,864
     66                         51,544                       478,764
     72                         61,588                       589,860
     88                         94,748                       989,867
     90                        265,336                     2,879,865
     99                        800,054                     9,898,956
    108                      3,750,017                    49,989,744
    126                      6,292,149                    88,996,914
    135                     44,194,186                   689,988,915
    144                     55,065,654                   879,987,906
    150                     61,074,615                   989,888,823
    153                    179,838,772                 2,998,895,823
    192                    399,977,785                 6,998,899,824
    201                    497,993,710                 8,889,999,624
    234                    502,602,764                 8,988,988,866
    258                    547,594,831                 9,879,997,824
    276                  1,039,028,518                18,879,988,824

zkl[edit]

harshadW:=[1..].tweak(fcn(n){ if(n%(n.split().sum(0))) Void.Skip else n });
harshadW:=Walker.zero().tweak(fcn(go){ // faster than one liner, fewer calls
foreach h in ([go.value..]){ // spin
s,t := 0,h; while(t){ s+=t%10; t/=10 } // sum of digits
if(0 == h%s){ go.set(h+1); return(h) }
}
}.fp(Ref(1)));
println("gap size    Niven index      Niven #");
prev,gap := harshadW.next(),0;
while(harshadW.n<=10_000_000){
if( (g:=(h:=harshadW.next()) - prev) > gap){
println("%5,d %14,d %15,d".fmt(g, harshadW.n - 1, prev));
gap=g;
}
prev=h;
}
Output:
gap size    Niven index      Niven #
    1              1               1
    2             10              10
    6             11              12
    7             26              63
    8             28              72
   10             32              90
   12             83             288
   14            102             378
   18            143             558
   23            561           2,889
   32            716           3,784
   36          1,118           6,480
   44          2,948          19,872
   45          4,194          28,971
   54          5,439          38,772
   60         33,494         297,864
   66         51,544         478,764
   72         61,588         589,860
   88         94,748         989,867
   90        265,336       2,879,865
   99        800,054       9,898,956
  108      3,750,017      49,989,744
  126      6,292,149      88,996,914