Increasing gaps between consecutive Niven numbers
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
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. <lang go>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 }
}</lang>
- 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
<lang julia>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)
</lang>
- 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
Perl 6
<lang perl6>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;
}</lang>
- 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
Replaced sum(digits) in the original with sd, otherwise no great attempt to optimise <lang Phix>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</lang>
- 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
add digits serially
<lang rexx>/*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</lang>
- 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
add digits in chunks
The method used is to break a number into 5-digit (decimal) chunks (or less), and those chunks have been pre-computed to find their digit sum. Also pre-computed were chunks that had various lengths of chucks with leading zeros (from none to four), such that 3 03 003 0003 and 00003 all have the same digital sum. Same thing with 478 0478 and 00478. This method could've been expanded to six-digit chunks, at the expense of real memory.
It is about four times faster than the 1st REXX version.
The "chunk" method is essentially a sum of several chunks, the sums are found by a table lookup (associative array in REXX). <lang rexx>/*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= 1000000000000 /*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 /*set all values to zero for chunk sums*/
do j=1 for 99999 /*pre─compute sums for #a up to 5 digs.*/ parse var j 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*/ /*do sum of digits the hard way for now*/ @.j= sum /*assume a sum for a particular number.*/ if j>9999 then iterate /*if J has five digits or more, skip.*/ do zz= length(j)+1 to 4 /*handle all J's with leading zeros. */ jz= right(j, zz, 0) /*also add leading zeros from some J's.*/ if @.jz==0 then @.jz= sum /*assign a sum to 000xx for instance.*/ end /*zz*/ end /*j*/
- = 0 /*#: is the index of a Niven number. */
do n=1 /*◄───── let's go Niven number hunting.*/ parse var n q1 +5 q2 +5 q3 +5 q4 +5 q4 +5 q6 /*break apart N into 5─digit chunks. */ sum= @.q1 + @.q2 + @.q3 + @.q4 + @.q5 + @.q6 /*add the 5─digit chunks to compute sum*/ if n//sum > 0 then iterate /*is N not divisible by its sum? Skip.*/ #= # + 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</lang>
- output is identical to the 1st REXX version.
zkl
<lang zkl>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)));</lang> <lang zkl>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;
}</lang>
- 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