Increasing gaps between consecutive Niven numbers: Difference between revisions
added RPL |
Added Sidef |
||
Line 2,308:
31 258 547,594,831 9,879,997,824
32 276 1,039,028,518 18,879,988,824
</pre>
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">var threshold = 10_000_000
say "Gap Index of gap Starting Niven"
for (var (n=1, index=0, gap=0, prev=1); index <= threshold; ++n) {
n.is_div(n.digits_sum) || next
if ((var diff = (n - prev)) > gap) {
gap = diff
printf("%3d %15s %15s\n", gap, index, prev)
}
prev = n
++index
}</syntaxhighlight>
{{out}}
<pre>
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 2889
32 716 3784
36 1118 6480
44 2948 19872
45 4194 28971
54 5439 38772
60 33494 297864
66 51544 478764
72 61588 589860
88 94748 989867
90 265336 2879865
99 800054 9898956
108 3750017 49989744
126 6292149 88996914
</pre>
|
Revision as of 19:42, 4 July 2024
You are encouraged to solve this task according to the task description, using any language you may know.
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
11l
F digit_sum(=n, =sum)
sum++
L n > 0 & n % 10 == 0
sum -= 9
n /= 10
R sum
V previous = 1
V gap = 0
V s = 0
V niven_index = 0
V gap_index = 1
print(‘Gap index Gap Niven index Niven number’)
V niven = 1
L gap_index <= 22
s = digit_sum(niven, s)
I niven % s == 0
I niven > previous + gap
gap = niven - previous
print(‘#9 #4 #13 #11’.format(gap_index, gap, niven_index, previous))
gap_index++
previous = niven
niven_index++
niven++
- Output:
Gap index Gap Niven index Niven number 1 1 1 1 2 2 10 10 3 6 11 12 4 7 26 63 5 8 28 72 6 10 32 90 7 12 83 288 8 14 102 378 9 18 143 558 10 23 561 2889 11 32 716 3784 12 36 1118 6480 13 44 2948 19872 14 45 4194 28971 15 54 5439 38772 16 60 33494 297864 17 66 51544 478764 18 72 61588 589860 19 88 94748 989867 20 90 265336 2879865 21 99 800054 9898956 22 108 3750017 49989744
ALGOL 68
BEGIN # show where the gaps increase in the series of Niven numbers #
# ( numbers divisible by the sum of their digits ) #
INT n count := 0;
INT g count := 0;
INT n gap := 0;
INT this n := 1;
print( ( " Gap Gap Niven Niven Next", newline ) );
print( ( "Index Value Index Number Niven Number", newline ) );
print( ( "----- ----- -------- --------- ------------", newline ) );
INT t8 := 0;
FOR d0 FROM 0 TO 9 DO
FOR d1 FROM 0 TO 9 DO
INT s1 = d0 + d1;
FOR d2 FROM 0 TO 9 DO
INT s2 = s1 + d2;
FOR d3 FROM 0 TO 9 DO
INT s3 = s2 + d3;
FOR d4 FROM 0 TO 9 DO
INT s4 = s3 + d4;
FOR d5 FROM 0 TO 9 DO
INT s5 = s4 + d5;
FOR d6 FROM 0 TO 9 DO
INT s6 = s5 + d6;
FOR d7 FROM 0 TO 9 DO
INT s7 = s6 + d7;
FOR d8 FROM 0 TO 9 DO
INT s8 = s7 + d8;
IF s8 /= 0 THEN
t8 +:= 1;
IF t8 MOD s8 = 0 THEN
# have a Niven number #
INT this gap = t8 - this n;
IF this gap > n gap THEN
# found a larger gap #
g count +:= 1;
n gap := this gap;
print( ( whole( g count, -5 )
, whole( n gap, -6 )
, whole( n count, -9 )
, whole( this n, -10 )
, " "
, whole( t8, 0 )
, newline
)
)
FI;
n count +:= 1;
this n := t8
FI
FI
OD # d8 #
OD # d7 #
OD # d6 #
OD # d5 #
OD # d4 #
OD # d3 #
OD # d2 #
OD # d1 #
OD # d0 #
END
- Output:
Gap Gap Niven Niven Next Index Value Index Number Niven Number ----- ----- -------- --------- ------------ 1 1 1 1 2 2 2 10 10 12 3 6 11 12 18 4 7 26 63 70 5 8 28 72 80 6 10 32 90 100 7 12 83 288 300 8 14 102 378 392 9 18 143 558 576 10 23 561 2889 2912 11 32 716 3784 3816 12 36 1118 6480 6516 13 44 2948 19872 19916 14 45 4194 28971 29016 15 54 5439 38772 38826 16 60 33494 297864 297924 17 66 51544 478764 478830 18 72 61588 589860 589932 19 88 94748 989867 989955 20 90 265336 2879865 2879955 21 99 800054 9898956 9899055 22 108 3750017 49989744 49989852 23 126 6292149 88996914 88997040 24 135 44194186 689988915 689989050 25 144 55065654 879987906 879988050 26 150 61074615 989888823 989888973
AWK
# syntax: GAWK -f INCREASING_GAPS_BETWEEN_CONSECUTIVE_NIVEN_NUMBERS.AWK
# converted from C
BEGIN {
gap_index = 1
previous = 1
print("Gap index Gap Niven index Niven number")
print("--------- --- ----------- ------------")
for (niven=1; gap_index<=22; niven++) {
sum = digit_sum(niven,sum)
if (divisible(niven,sum)) {
if (niven > previous + gap) {
gap = niven - previous
printf("%9d %4d %12d %13d\n",gap_index++,gap,niven_index,previous)
}
previous = niven
niven_index++
}
}
exit(0)
}
function digit_sum(n,sum) {
# returns the sum of the digits of n given the sum of the digits of n - 1
sum++
while (n > 0 && n % 10 == 0) {
sum -= 9
n = int(n / 10)
}
return(sum)
}
function divisible(n,d) {
if (and(d,1) == 0 && and(n,1) == 1) {
return(0)
}
return(n % d == 0)
}
- Output:
Gap index Gap Niven index Niven number --------- --- ----------- ------------ 1 1 1 1 2 2 10 10 3 6 11 12 4 7 26 63 5 8 28 72 6 10 32 90 7 12 83 288 8 14 102 378 9 18 143 558 10 23 561 2889 11 32 716 3784 12 36 1118 6480 13 44 2948 19872 14 45 4194 28971 15 54 5439 38772 16 60 33494 297864 17 66 51544 478764 18 72 61588 589860 19 88 94748 989867 20 90 265336 2879865 21 99 800054 9898956 22 108 3750017 49989744
BASIC256
function digit_sum(n, sum)
# devuelve la suma de los dígitos de n dada la suma de los dígitos de n - 1
sum ++
while (n > 0 and n mod 10 = 0)
sum -= 9
n = int(n / 10)
end while
return sum
end function
function divisible(n, d)
if ((d mod 1) = 0) and ((n mod 1) = 1) then
return 0
end if
return (n mod d = 0)
end function
global sum
sum = 0
gap = 0 : niven = 0 : niven_index = 0
gap_index = 0
previous = 1
print "Gap index Gap Niven index Niven number"
print "--------- --- ----------- ------------"
for niven = 1 to 1000000
sum = digit_sum(niven, sum)
if divisible(niven, sum) then
if (niven > previous + gap) then
gap_index += 1
gap = niven - previous
print gap_index, gap, niven_index, previous
end if
previous = niven
niven_index ++
end if
next niven
end
C
#include <locale.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
// Returns the sum of the digits of n given the
// sum of the digits of n - 1
uint64_t digit_sum(uint64_t n, uint64_t sum) {
++sum;
while (n > 0 && n % 10 == 0) {
sum -= 9;
n /= 10;
}
return sum;
}
inline bool divisible(uint64_t n, uint64_t d) {
if ((d & 1) == 0 && (n & 1) == 1)
return false;
return n % d == 0;
}
int main() {
setlocale(LC_ALL, "");
uint64_t previous = 1, gap = 0, sum = 0;
int niven_index = 0, gap_index = 1;
printf("Gap index Gap Niven index Niven number\n");
for (uint64_t niven = 1; gap_index <= 32; ++niven) {
sum = digit_sum(niven, sum);
if (divisible(niven, sum)) {
if (niven > previous + gap) {
gap = niven - previous;
printf("%'9d %'4llu %'14d %'15llu\n", gap_index++,
gap, niven_index, previous);
}
previous = niven;
++niven_index;
}
}
return 0;
}
- Output:
Gap index Gap Niven index Niven number 1 1 1 1 2 2 10 10 3 6 11 12 4 7 26 63 5 8 28 72 6 10 32 90 7 12 83 288 8 14 102 378 9 18 143 558 10 23 561 2,889 11 32 716 3,784 12 36 1,118 6,480 13 44 2,948 19,872 14 45 4,194 28,971 15 54 5,439 38,772 16 60 33,494 297,864 17 66 51,544 478,764 18 72 61,588 589,860 19 88 94,748 989,867 20 90 265,336 2,879,865 21 99 800,054 9,898,956 22 108 3,750,017 49,989,744 23 126 6,292,149 88,996,914 24 135 44,194,186 689,988,915 25 144 55,065,654 879,987,906 26 150 61,074,615 989,888,823 27 153 179,838,772 2,998,895,823 28 192 399,977,785 6,998,899,824 29 201 497,993,710 8,889,999,624 30 234 502,602,764 8,988,988,866 31 258 547,594,831 9,879,997,824 32 276 1,039,028,518 18,879,988,824
C++
#include <cstdint>
#include <iomanip>
#include <iostream>
// Returns the sum of the digits of n given the
// sum of the digits of n - 1
uint64_t digit_sum(uint64_t n, uint64_t sum) {
++sum;
while (n > 0 && n % 10 == 0) {
sum -= 9;
n /= 10;
}
return sum;
}
inline bool divisible(uint64_t n, uint64_t d) {
if ((d & 1) == 0 && (n & 1) == 1)
return false;
return n % d == 0;
}
int main() {
// Print numbers with commas
std::cout.imbue(std::locale(""));
uint64_t previous = 1, gap = 0, sum = 0;
int niven_index = 0, gap_index = 1;
std::cout << "Gap index Gap Niven index Niven number\n";
for (uint64_t niven = 1; gap_index <= 32; ++niven) {
sum = digit_sum(niven, sum);
if (divisible(niven, sum)) {
if (niven > previous + gap) {
gap = niven - previous;
std::cout << std::setw(9) << gap_index++
<< std::setw(5) << gap
<< std::setw(15) << niven_index
<< std::setw(16) << previous << '\n';
}
previous = niven;
++niven_index;
}
}
return 0;
}
- Output:
Gap index Gap Niven index Niven number 1 1 1 1 2 2 10 10 3 6 11 12 4 7 26 63 5 8 28 72 6 10 32 90 7 12 83 288 8 14 102 378 9 18 143 558 10 23 561 2,889 11 32 716 3,784 12 36 1,118 6,480 13 44 2,948 19,872 14 45 4,194 28,971 15 54 5,439 38,772 16 60 33,494 297,864 17 66 51,544 478,764 18 72 61,588 589,860 19 88 94,748 989,867 20 90 265,336 2,879,865 21 99 800,054 9,898,956 22 108 3,750,017 49,989,744 23 126 6,292,149 88,996,914 24 135 44,194,186 689,988,915 25 144 55,065,654 879,987,906 26 150 61,074,615 989,888,823 27 153 179,838,772 2,998,895,823 28 192 399,977,785 6,998,899,824 29 201 497,993,710 8,889,999,624 30 234 502,602,764 8,988,988,866 31 258 547,594,831 9,879,997,824 32 276 1,039,028,518 18,879,988,824
Cowgol
The largest integer Cowgol supports is 32-bit, so this code prints up to the 27th gap (the last one where the Niven number fits in the integer type).
include "cowgol.coh";
# print uint32 right-aligned in column, with
# thousands separators
sub print_col(num: uint32, width: uint8) is
# maximum integer is 4,294,967,296 for length 13,
# plus one extra for the zero terminator
var buf: uint8[14];
var start := &buf[0];
var last := UIToA(num, 10, &buf[0]);
# right-align and add separators
var right := &buf[13];
var th: uint8 := 3;
while last >= start loop
[right] := [last];
right := @prev right;
last := @prev last;
if th == 0 and last >= start then
# add separator every 3 characters
[right] := ',';
right := @prev right;
th := 2;
else
th := th - 1;
end if;
end loop;
# print the result and spaces
var size := (13 - (right - start)) as uint8;
while width >= size loop
print_char(' ');
width := width-1;
end loop;
print(@next right);
end sub;
# returns sum of digits of n, given sum of digits of n-1
sub digit_sum(n: uint32, prev: uint32): (sum: uint32) is
sum := prev + 1;
while n > 0 and n % 10 == 0 loop
sum := sum - 9;
n := n / 10;
end loop;
end sub;
var prev: uint32 := 1;
var gap: uint32 := 0;
var sum: uint32 := 0;
var idx: uint32 := 0;
var gap_idx: uint8 := 1;
var niven: uint32 := 1;
print("Gap index Gap Niven index Niven number\n");
while gap_idx <= 27 loop
sum := digit_sum(niven, sum);
if (not (sum & 1 == 0 and niven & 1 == 1))
and (niven % sum == 0) then
if niven > prev + gap then
gap := niven - prev;
print_col(gap_idx as uint32, 9);
gap_idx := gap_idx + 1;
print_col(gap, 5);
print_col(idx, 15);
print_col(prev, 16);
print_nl();
end if;
prev := niven;
idx := idx + 1;
end if;
niven := niven + 1;
end loop;
- Output:
Gap index Gap Niven index Niven number 1 1 1 1 2 2 10 10 3 6 11 12 4 7 26 63 5 8 28 72 6 10 32 90 7 12 83 288 8 14 102 378 9 18 143 558 10 23 561 2,889 11 32 716 3,784 12 36 1,118 6,480 13 44 2,948 19,872 14 45 4,194 28,971 15 54 5,439 38,772 16 60 33,494 297,864 17 66 51,544 478,764 18 72 61,588 589,860 19 88 94,748 989,867 20 90 265,336 2,879,865 21 99 800,054 9,898,956 22 108 3,750,017 49,989,744 23 126 6,292,149 88,996,914 24 135 44,194,186 689,988,915 25 144 55,065,654 879,987,906 26 150 61,074,615 989,888,823 27 153 179,838,772 2,998,895,823
Delphi
Because the code requires almost two minutes to run, it has optional callback that supplies information that can be used to power a progress bar.
function SumDigits(N: integer): integer;
{Sum the integers in a number}
var T: integer;
begin
Result:=0;
repeat
begin
T:=N mod 10;
N:=N div 10;
Result:=Result+T;
end
until N<1;
end;
function IsNiven(N: integer): boolean;
{Test if N is evenly divisible by sum}
{i.e. is it a Niven Number}
var Sum: integer;
begin
Sum:=SumDigits(N);
Result:=(N mod Sum)=0;
end;
function GetNextNiven(Start: integer): integer;
{Get the next Niven number after Start}
begin
repeat Inc(Start)
until IsNiven(Start);
Result:=Start;
end;
procedure ShowNivenGaps(Memo: TMemo; Prog: TProgress);
{Show when gaps between sucessive Niven Numbers changes}
var I: integer;
var N1,N2,Gap: integer;
var Cnt: integer;
const Limit = 65000000;
begin
Memo.Lines.Add(' Gap Gap Niven Niven Next');
Memo.Lines.Add('Index Value Index Number Niven Number');
Memo.Lines.Add('----- ----- -------- --------- ------------');
Gap:=0; Cnt:=0;
N1:=GetNextNiven(0);
for I:=1 to Limit do
begin
{Get next Niven and test if Gap has changed}
N2:=GetNextNiven(N1);
if (N2-N1)>Gap then
begin
Gap:=N2-N1;
Inc(Cnt);
Memo.Lines.Add(Format('%5d%6d%15.0n%15.0n%15.0n',[Cnt,Gap,I+0.0,N1+0.0,N2+0.0]));
end;
N1:=N2;
if Assigned(Prog) and ((I mod 100000)=0) then Prog(MulDiv(100,I,Limit));
end;
end;
- Output:
Gap Gap Niven Niven Next Index Value Index Number Niven Number ----- ----- -------- --------- ------------ 1 1 1 1 2 2 2 10 10 12 3 6 11 12 18 4 7 26 63 70 5 8 28 72 80 6 10 32 90 100 7 12 83 288 300 8 14 102 378 392 9 18 143 558 576 10 23 561 2,889 2,912 11 32 716 3,784 3,816 12 36 1,118 6,480 6,516 13 44 2,948 19,872 19,916 14 45 4,194 28,971 29,016 15 54 5,439 38,772 38,826 16 60 33,494 297,864 297,924 17 66 51,544 478,764 478,830 18 72 61,588 589,860 589,932 19 88 94,748 989,867 989,955 20 90 265,336 2,879,865 2,879,955 21 99 800,054 9,898,956 9,899,055 22 108 3,750,017 49,989,744 49,989,852 23 126 6,292,149 88,996,914 88,997,040 24 135 44,194,186 689,988,915 689,989,050 25 144 55,065,654 879,987,906 879,988,050 26 150 61,074,615 989,888,823 989,888,973
EasyLang
func digsum n sum .
sum += 1
while n > 0 and n mod 10 = 0
sum -= 9
n = n div 10
.
return sum
.
func divisible n d .
if d mod 2 = 0 and n mod 2 = 1
return 0
.
return if n mod d = 0
.
numfmt 0 8
previous = 1
print " Gap index Gap Niven index Niven number"
print " --------- --- ----------- ------------"
for niven = 1 to 10000000
sum = digsum niven sum
if divisible niven sum = 1
if niven > previous + gap
gap_index += 1
gap = niven - previous
print gap_index & gap & " " & niven_index & " " & previous
.
previous = niven
niven_index += 1
.
.
- Output:
Gap index Gap Niven index Niven number --------- --- ----------- ------------ 1 1 1 1 2 2 10 10 3 6 11 12 4 7 26 63 5 8 28 72 6 10 32 90 7 12 83 288 8 14 102 378 9 18 143 558 10 23 561 2889 11 32 716 3784 12 36 1118 6480 13 44 2948 19872 14 45 4194 28971 15 54 5439 38772 16 60 33494 297864 17 66 51544 478764 18 72 61588 589860 19 88 94748 989867 20 90 265336 2879865 21 99 800054 9898956
Fortran
program nivengaps
implicit none
integer*8 prev /1/, gap /0/, sum /0/
integer*8 nividx /0/, niven /1/
integer gapidx /1/
character*13 idxfmt
character*14 nivfmt
write (*,*) 'Gap no Gap Niven index Niven number '
write (*,*) '------ --- ------------- --------------'
10 call divsum(niven, sum)
if (mod(niven, sum) .EQ. 0) then
if (niven .GT. prev + gap) then
gap = niven - prev
call fmtint(nividx,13,idxfmt)
call fmtint(prev,14,nivfmt)
write (*,20) gapidx,gap,idxfmt,nivfmt
gapidx = gapidx + 1
end if
prev = niven
nividx = nividx + 1
end if
niven = niven + 1
if (gapidx .LE. 32) go to 10
stop
20 format (i7,' ',i3,' ',a13,' ',a14)
end program
C Sum of divisors of NN, given the sum of divisors of NN-1
subroutine divsum(nn,sum)
implicit none
integer*8 n,nn,sum
n = nn
sum = sum + 1
30 if (n.GT.0 .AND. mod(n,10).EQ.0) then
sum = sum - 9
n = n / 10
go to 30
end if
end subroutine
integer*8 function mod(a,b)
implicit none
integer*8 a,b
mod = a - a/b * b
end function
C Format a positive integer with ',' as the thousands separator.
subroutine fmtint(num, len, str)
implicit none
integer*8 n, num
integer pos, len, th
character(*) str
n=num
pos=len
th=2
40 if (pos.GT.0) then
if (n.EQ.0) then
str(pos:pos) = ' '
else
str(pos:pos) = achar(mod(n,10) + iachar('0'))
if (th.EQ.0 .AND. n.GE.10 .AND. pos.GT.1) then
th = 2
pos = pos-1
str(pos:pos) = ','
else
th = th-1
end if
end if
pos = pos - 1
n = n/10
go to 40
end if
end subroutine
- Output:
Gap no Gap Niven index Niven number ------ --- ------------- -------------- 1 1 1 1 2 2 10 10 3 6 11 12 4 7 26 63 5 8 28 72 6 10 32 90 7 12 83 288 8 14 102 378 9 18 143 558 10 23 561 2,889 11 32 716 3,784 12 36 1,118 6,480 13 44 2,948 19,872 14 45 4,194 28,971 15 54 5,439 38,772 16 60 33,494 297,864 17 66 51,544 478,764 18 72 61,588 589,860 19 88 94,748 989,867 20 90 265,336 2,879,865 21 99 800,054 9,898,956 22 108 3,750,017 49,989,744 23 126 6,292,149 88,996,914 24 135 44,194,186 689,988,915 25 144 55,065,654 879,987,906 26 150 61,074,615 989,888,823 27 153 179,838,772 2,998,895,823 28 192 399,977,785 6,998,899,824 29 201 497,993,710 8,889,999,624 30 234 502,602,764 8,988,988,866 31 258 547,594,831 9,879,997,824 32 276 1,039,028,518 18,879,988,824
FreeBASIC
Function digit_sum(n As Uinteger, sum As Ulong) As Ulong
' devuelve la suma de los dígitos de n dada la suma de los dígitos de n - 1
sum += 1
While (n > 0 And n Mod 10 = 0)
sum -= 9
n = Int(n / 10)
Wend
Return sum
End Function
Function divisible(n As Uinteger, d As Uinteger) As Boolean
If ((d Mod 1) = 0) And ((n Mod 1) = 1) Then
Return 0
End If
Return (n Mod d = 0)
End Function
Dim As Ulong gap_index = 0
Dim As Ulong previous = 1
Dim As Uinteger gap
Dim As Ulong niven_index
Print "Gap index Gap Niven index Niven number"
Print "--------- --- ----------- ------------"
For niven As Uinteger = 1 To 100000000
Dim As Ulong sum = digit_sum(niven,sum)
If divisible(niven, sum) Then
If (niven > previous + gap) Then
gap_index += 1
gap = niven - previous
Print Using "######### ### ###,###,### ####,###,###"; gap_index; gap; niven_index; previous
End If
previous = niven
niven_index += 1
End If
Next niven
Sleep
- Output:
Gap index Gap Niven index Niven number --------- --- ----------- ------------ 1 1 1 1 2 2 10 10 3 6 11 12 4 7 26 63 5 8 28 72 6 10 32 90 7 12 83 288 8 14 102 378 9 18 143 558 10 23 561 2,889 11 32 716 3,784 12 36 1,118 6,480 13 44 2,948 19,872 14 45 4,194 28,971 15 54 5,439 38,772 16 60 33,494 297,864 17 66 51,544 478,764 18 72 61,588 589,860 19 88 94,748 989,867 20 90 265,336 2,879,865 21 99 800,054 9,898,956 22 108 3,750,017 49,989,744 23 126 6,292,149 88,996,914
FutureBasic
Note: Computation time rises exponentially after the first 22 iterations.
local fn DigitSum( n as UInt64, sum as UInt64 ) as UInt64
sum++
while ( n > 0 and n mod 10 == 0 )
sum -= 9
n = n / 10
wend
end fn = sum
local fn IsDivisible( n as UInt64, d as UInt64 ) as BOOL
BOOL result
if ( ( d and 1 ) == 0 and ( n and 1 ) == 1 ) then result = NO : exit fn
result = n mod d == 0
end fn = result
local fn DoIt
UInt64 niven, previous = 1, gap = 0, sum = 0
long niven_index = 0, gap_index = 1
printf( @"Index Gap Niven index Niven number" )
printf( @"----- --- ----------- ------------" )
for niven = 1 to gap_index <= 24
sum = fn DigitSum( niven, sum )
if ( fn IsDivisible( niven, sum ) )
if ( niven > previous + gap )
gap = niven - previous
printf @"%3d %6llu %13d %15llu", gap_index, gap, niven_index, previous
gap_index++
end if
previous = niven
niven_index++
end if
next
end fn
fn DoIt
HandleEvents
- Output:
Index Gap Niven index Niven number ----- --- ----------- ------------ 1 1 1 1 2 2 10 10 3 6 11 12 4 7 26 63 5 8 28 72 6 10 32 90 7 12 83 288 8 14 102 378 9 18 143 558 10 23 561 2889 11 32 716 3784 12 36 1118 6480 13 44 2948 19872 14 45 4194 28971 15 54 5439 38772 16 60 33494 297864 17 66 51544 478764 18 72 61588 589860 19 88 94748 989867 20 90 265336 2879865 21 99 800054 9898956 22 108 3750017 49989744 23 126 6292149 88996914 24 135 44194186 689988915
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.
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
Haskell
{-# LANGUAGE NumericUnderscores #-}
import Control.Monad (guard)
import Text.Printf (printf)
import Data.List (intercalate, unfoldr)
import Data.List.Split (chunksOf)
import Data.Tuple (swap)
nivens :: [Int]
nivens = [1..] >>= \n -> guard (n `rem` digitSum n == 0) >> [n]
where
digitSum = sum . unfoldr (\x -> guard (x > 0) >> pure (swap $ x `quotRem` 10))
findGaps :: [(Int, Int, Int)]
findGaps = go (zip [1..] nivens) 0
where
go [] n = []
go r@((c, currentNiven):(_, nextNiven):xs) lastGap
| gap > lastGap = (gap, c, currentNiven) : go (tail r) gap
| otherwise = go (tail r) lastGap
where
gap = nextNiven - currentNiven
go (x:xs) _ = []
thousands :: Int -> String
thousands = reverse . intercalate "," . chunksOf 3 . reverse . show
main :: IO ()
main = do
printf row "Gap" "Index of Gap" "Starting Niven"
mapM_ (\(gap, gapIndex, niven) -> printf row (show gap) (thousands gapIndex) (thousands niven))
$ takeWhile (\(_, gapIndex, _) -> gapIndex < 10_000_000) findGaps
where
row = "%5s%15s%15s\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
J
tasks=: (gap , (,:~ index))@:niven
gap=: 0 ,~ 2 -~/\ ]
index=: i.@:#
niven=: I.@:nivenQ@:i.
nivenQ=: 0 = (|~ ([: (+/"1) 10&#.^:_1))
assert 1 0 1 -: nivenQ 10 11 12 NB. demonstrate correct niven test
assert 1 = +/ 10 12 E. niven 100 NB. the sublist 10 12 occurs once in niven numbers less than 100
assert 0 1 6 90 -: gap 1 2 8 98 NB. show infix swapped subtractions
NB. demonstrate the array tasks 100 NB. tasks constructs an array with the desired values 1 1 1 1 1 1 1 1 1 1 2 6 2 1 3 3 3 6 4 2 3 3 2 4 6 3 7 2 8 1 3 6 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 0 1 2 3 4 5 6 7 8 9 10 12 18 20 21 24 27 30 36 40 42 45 48 50 54 60 63 70 72 80 81 84 90 NB. extract the report from a sufficiently large space TASK=:({~(0 1 2<@;_1,~(i.([:~.>./\)))@:{.)0 1}.tasks 200000000 NB. present result (<;._2'title; task;greatest niven;'),(<];._2'gap;index;niven;'),.(0 23,:3 23)<;.3 TASK ┌─────┬───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┬──────────────┐ │title│ task │greatest niven│ ├─────┼───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┼──────────────┤ │gap │1 2 6 7 8 10 12 14 18 23 32 36 44 45 54 60 66 72 88 90 99 108 126│ 0 │ │index│1 10 11 26 28 32 83 102 143 561 716 1118 2948 4194 5439 33494 51544 61588 94748 265336 800054 3750017 6292149│ 13694681 │ │niven│1 10 12 63 72 90 288 378 558 2889 3784 6480 19872 28971 38772 297864 478764 589860 989867 2879865 9898956 49989744 88996914│199999936 │ └─────┴───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┴──────────────┘
J tokens are either isolated ASCII symbols or end with a suffix either `.' or ':' . Verbs return nouns. The sentence of nouns and verbs ~.>./\2-~/\A evaluate from right to left.
( ~. ( >./\ ( 2 -~/\ A ) ) )
Given that
A
names a list of Niven numbers
`2 -~/\ A' finds the difference between successive pairs of A. In 2 -~/\ A the verb -~/\ surrounded by nouns is dyadic, which is to do -~/ on the length 2 infixes of A. Consuming the 2 and A, infix adverb \ passes length 2 vectors of items of A to the verb -~/ . Adverb / inserts the verb - between the items of the vector, which it then evaluates since there's no more...except that we want a[i+1]-a[i], which explains the passive ~ adverb to swap the arguments.
`>./\' applied to the successive difference: In this instance there isn't a given infix length, hence the \ here is monadic "prefixes" adverb. Dyadic `x >. y' is the maximum of x and y. Inserting >. to the prefixes results in a vector of maximum value to that point.
Finally, the monadic ~. evaluates the nub (set) of the items presented to it.
Java
public class NivenNumberGaps {
// Title: Increasing gaps between consecutive Niven numbers
public static void main(String[] args) {
long prevGap = 0;
long prevN = 1;
long index = 0;
System.out.println("Gap Gap Index Starting Niven");
for ( long n = 2 ; n < 20_000_000_000l ; n++ ) {
if ( isNiven(n) ) {
index++;
long curGap = n - prevN;
if ( curGap > prevGap ) {
System.out.printf("%3d %,13d %,15d%n", curGap, index, prevN);
prevGap = curGap;
}
prevN = n;
}
}
}
public static boolean isNiven(long n) {
long sum = 0;
long nSave = n;
while ( n > 0 ) {
sum += n % 10;
n /= 10;
}
return nSave % sum == 0;
}
}
- Output:
Gap Gap Index 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
jq
Adapted from C
Works with gojq, the Go implementation of jq
In this entry, computation continues in accordance with the task description, that is until a specified Niven number is reached.
To have computation continue indefinitely, call the `nivens` generator with `null` or `infinite` as input, e.g.:
infinite | nivens
Preliminaries
def add(s): reduce s as $x (null; . + $x);
def digit_sum:
def digits: tostring | explode[] | [.] | implode | tonumber;
add(digits);
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;
Niven Numbers
# input: the largest Niven number to be considered (null => infinite)
# output: a stream of informative JSON objects -
# {gap_index, gap, niven_index, previous}
def nivens:
(. // infinite) as $limit
| { gap: 0,
gap_index: 1,
niven: 1,
niven_index: 1}
| foreach range(2; $limit+1) as $n (.;
.emit = false
| if $n % ($n | digit_sum) == 0
then if $n > .niven + .gap
then .gap = $n - .niven
| .emit = {gap_index, gap, niven_index, niven}
| .gap_index += 1
else .
end
| .niven = $n
| .niven_index += 1
else .
end;
select(.emit).emit );
"Gap index Gap Niven index Niven number",
"--------- --- ----------- ------------",
( 1E7 | nivens
| "\(.gap_index|lpad(9)) \(.gap|lpad(4)) \(.niven_index|lpad(12)) \(.niven|lpad(13))" )
- Output:
Gap index Gap Niven index Niven number --------- --- ----------- ------------ 1 1 1 1 2 2 10 10 3 6 11 12 4 7 26 63 5 8 28 72 6 10 32 90 7 12 83 288 8 14 102 378 9 18 143 558 10 23 561 2889 11 32 716 3784 12 36 1118 6480 13 44 2948 19872 14 45 4194 28971 15 54 5439 38772 16 60 33494 297864 17 66 51544 478764 18 72 61588 589860 19 88 94748 989867 20 90 265336 2879865 21 99 800054 9898956 22 108 3750017 49989744
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)
- 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
MAD
The original hardware MAD ran on had 36-bit words, so in theory it could calculate 32 gaps. However, that takes a couple of minutes even on modern hardware, so that would probably not count as "practical" to actually try on an IBM 704. Therefore, this program only prints as many as required by the task.
Furthermore, the optimization in the divisibility check that others do here (checking divisibility by 2 using bitwise operations), has to be left out since MAD does not have bitwise operations. It's possible to fake them using division, but that would not be much of an optimization.
NORMAL MODE IS INTEGER
INTERNAL FUNCTION REM.(A,B) = A-A/B*B
PRINT COMMENT $ GAP NO GAP NIVEN INDEX NIVEN NUMBER$
PRINT COMMENT $ ****** *** *********** ************$
VECTOR VALUES FMT = $I6,S2,I3,S2,I11,S2,I12*$
PREV = 1
GAP = 0
SUM = 0
NIVIX = 0
GAPIX = 1
THROUGH LOOP, FOR NIVEN=1, 1, GAPIX.G.22
SUM = SUM + 1
N = NIVEN
DSUM WHENEVER N.G.0 .AND. REM.(N,10).E.0
SUM = SUM - 9
N = N / 10
TRANSFER TO DSUM
END OF CONDITIONAL
WHENEVER REM.(NIVEN,SUM).E.0
WHENEVER NIVEN.G.PREV+GAP
GAP = NIVEN-PREV
PRINT FORMAT FMT,GAPIX,GAP,NIVIX,PREV
GAPIX = GAPIX + 1
END OF CONDITIONAL
PREV = NIVEN
NIVIX = NIVIX + 1
END OF CONDITIONAL
LOOP CONTINUE
END OF PROGRAM
- Output:
GAP NO GAP NIVEN INDEX NIVEN NUMBER ****** *** *********** ************ 1 1 1 1 2 2 10 10 3 6 11 12 4 7 26 63 5 8 28 72 6 10 32 90 7 12 83 288 8 14 102 378 9 18 143 558 10 23 561 2889 11 32 716 3784 12 36 1118 6480 13 44 2948 19872 14 45 4194 28971 15 54 5439 38772 16 60 33494 297864 17 66 51544 478764 18 72 61588 589860 19 88 94748 989867 20 90 265336 2879865 21 99 800054 9898956 22 108 3750017 49989744
Mathematica /Wolfram Language
ClearAll[NivenQ]
$HistoryLength = 0;
NivenQ[n_Integer] := Divisible[n, Total[IntegerDigits[n]]]
sel = Select[Range[100000000], NivenQ];
i = FoldPairList[{#2 > #1, Max[#1, #2]} &, 0, Differences[sel]];
gapindex = Range[Count[i, True]];
nivenindex = Pick[Range[Length[i]], i];
nivennumber = Pick[Most[sel], i];
gap = sel[[nivenindex + 1]] - sel[[nivenindex]];
Grid[{gapindex, gap, nivenindex, nivennumber} // Transpose // Prepend[{"gap index", "gap", "niven index", "niven number"}], Frame -> All]
- Output:
gap index gap niven index niven number 1 1 1 1 2 2 10 10 3 6 11 12 4 7 26 63 5 8 28 72 6 10 32 90 7 12 83 288 8 14 102 378 9 18 143 558 10 23 561 2889 11 32 716 3784 12 36 1118 6480 13 44 2948 19872 14 45 4194 28971 15 54 5439 38772 16 60 33494 297864 17 66 51544 478764 18 72 61588 589860 19 88 94748 989867 20 90 265336 2879865 21 99 800054 9898956 22 108 3750017 49989744 23 126 6292149 88996914
Nim
import strformat
func digitsSum(n, sum: uint64): uint64 =
## Returns the sum of the digits of n given the sum of the digits of n - 1.
result = sum + 1
var n = n
while n > 0 and n mod 10 == 0:
dec result, 9
n = n div 10
func divisible(n, d: uint64): bool {.inline.} =
if (d and 1) == 0 and (n and 1) == 1:
return false
result = n mod d == 0
when isMainModule:
echo "Gap index Gap Niven index Niven number"
var
niven, gap, sum, nivenIndex = 0u64
previous, gapIndex = 1u64
while gapIndex <= 32:
inc niven
sum = digitsSum(niven, sum)
if divisible(niven, sum):
if niven > previous + gap:
gap = niven - previous
echo fmt"{gapIndex:9d} {gap:4d} {nivenIndex:12d} {previous:13d}"
inc gapIndex
previous = niven
inc nivenIndex
- Output:
Gap index Gap Niven index Niven number 1 1 1 1 2 2 10 10 3 6 11 12 4 7 26 63 5 8 28 72 6 10 32 90 7 12 83 288 8 14 102 378 9 18 143 558 10 23 561 2889 11 32 716 3784 12 36 1118 6480 13 44 2948 19872 14 45 4194 28971 15 54 5439 38772 16 60 33494 297864 17 66 51544 478764 18 72 61588 589860 19 88 94748 989867 20 90 265336 2879865 21 99 800054 9898956 22 108 3750017 49989744 23 126 6292149 88996914 24 135 44194186 689988915 25 144 55065654 879987906 26 150 61074615 989888823 27 153 179838772 2998895823 28 192 399977785 6998899824 29 201 497993710 8889999624 30 234 502602764 8988988866 31 258 547594831 9879997824 32 276 1039028518 18879988824
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
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
Phix
Replaced sum(digits) in the original with sd, otherwise no great attempt to optimise
with javascript_semantics 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<=iff(platform()=JS?10_000_000: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)
Python
"""
Python implementation of
http://rosettacode.org/wiki/Increasing_gaps_between_consecutive_Niven_numbers
"""
# based on C example
# Returns the sum of the digits of n given the
# sum of the digits of n - 1
def digit_sum(n, sum):
sum += 1
while n > 0 and n % 10 == 0:
sum -= 9
n /= 10
return sum
previous = 1
gap = 0
sum = 0
niven_index = 0
gap_index = 1
print("Gap index Gap Niven index Niven number")
niven = 1
while gap_index <= 22:
sum = digit_sum(niven, sum)
if niven % sum == 0:
if niven > previous + gap:
gap = niven - previous;
print('{0:9d} {1:4d} {2:13d} {3:11d}'.format(gap_index, gap, niven_index, previous))
gap_index += 1
previous = niven
niven_index += 1
niven += 1
- Output:
Gap index Gap Niven index Niven number 1 1 1 1 2 2 10 10 3 6 11 12 4 7 26 63 5 8 28 72 6 10 32 90 7 12 83 288 8 14 102 378 9 18 143 558 10 23 561 2889 11 32 716 3784 12 36 1118 6480 13 44 2948 19872 14 45 4194 28971 15 54 5439 38772 16 60 33494 297864 17 66 51544 478764 18 72 61588 589860 19 88 94748 989867 20 90 265336 2879865 21 99 800054 9898956 22 108 3750017 49989744
Raku
(formerly Perl 6)
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
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
- 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
RPL
« →STR 0. 1. PICK3 SIZE FOR j OVER j DUP SUB STR→ + NEXT NIP » '∑DIG' STO « DO 1 + UNTIL DUPDUP ∑DIG / FP NOT END » 'NEXTNIVEN' STO « { { 1 1 1 1 } } 1 1 1 → res gap gapindex nivindex « 1 WHILE res SIZE 15 < REPEAT DUP NEXTNIVEN DUP2 SWAP - IF DUP gap > THEN DUP 'gap' STO 'gapindex' INCR SWAP nivindex 5 ROLL 4 →LIST 1 →LIST 'res' SWAP STO+ ELSE ROT DROP2 END 'nivindex' 1 STO+ END DROP res » » 'TASK' STO
- Output:
1: { { 1 1 1 1 } { 2 2 10 10 } { 3 6 11 12 } { 4 7 26 63 } { 5 8 28 72 } { 6 10 32 90 } { 7 12 83 288 } { 8 14 102 378 } { 9 18 143 558 } { 10 23 561 2889 } { 11 32 716 3784 } { 12 36 1118 6480 } { 13 44 2948 19872 } { 14 45 4194 28971 } { 15 54 5439 38772 } }
Ruby
nivens = Enumerator.new {|y| (1..).each {|n| y << n if n.remainder(n.digits.sum).zero?} }
cur_gap = 0
puts 'Gap Index of gap Starting Niven'
nivens.each_cons(2).with_index(1) do |(n1, n2), i|
break if i > 10_000_000
if n2-n1 > cur_gap then
printf "%3d %15s %15s\n", n2-n1, i, n1
cur_gap = n2-n1
end
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 2889 32 716 3784 36 1118 6480 44 2948 19872 45 4194 28971 54 5439 38772 60 33494 297864 66 51544 478764 72 61588 589860 88 94748 989867 90 265336 2879865 99 800054 9898956 108 3750017 49989744 126 6292149 88996914
Rust
// [dependencies]
// num-format = "0.4"
// Returns the sum of the digits of n given the
// sum of the digits of n - 1
fn digit_sum(mut n: u64, mut sum: u64) -> u64 {
sum += 1;
while n > 0 && n % 10 == 0 {
sum -= 9;
n /= 10;
}
sum
}
fn divisible(n: u64, d: u64) -> bool {
if (d & 1) == 0 && (n & 1) == 1 {
return false;
}
n % d == 0
}
fn main() {
use num_format::{Locale, ToFormattedString};
let mut previous = 1;
let mut gap = 0;
let mut sum = 0;
let mut niven_index = 0;
let mut gap_index = 1;
let mut niven = 1;
println!("Gap index Gap Niven index Niven number");
while gap_index <= 32 {
sum = digit_sum(niven, sum);
if divisible(niven, sum) {
if niven > previous + gap {
gap = niven - previous;
println!(
"{:9} {:4} {:>14} {:>15}",
gap_index,
gap,
niven_index.to_formatted_string(&Locale::en),
previous.to_formatted_string(&Locale::en)
);
gap_index += 1;
}
previous = niven;
niven_index += 1;
}
niven += 1;
}
}
- Output:
Gap index Gap Niven index Niven number 1 1 1 1 2 2 10 10 3 6 11 12 4 7 26 63 5 8 28 72 6 10 32 90 7 12 83 288 8 14 102 378 9 18 143 558 10 23 561 2,889 11 32 716 3,784 12 36 1,118 6,480 13 44 2,948 19,872 14 45 4,194 28,971 15 54 5,439 38,772 16 60 33,494 297,864 17 66 51,544 478,764 18 72 61,588 589,860 19 88 94,748 989,867 20 90 265,336 2,879,865 21 99 800,054 9,898,956 22 108 3,750,017 49,989,744 23 126 6,292,149 88,996,914 24 135 44,194,186 689,988,915 25 144 55,065,654 879,987,906 26 150 61,074,615 989,888,823 27 153 179,838,772 2,998,895,823 28 192 399,977,785 6,998,899,824 29 201 497,993,710 8,889,999,624 30 234 502,602,764 8,988,988,866 31 258 547,594,831 9,879,997,824 32 276 1,039,028,518 18,879,988,824
Sidef
var threshold = 10_000_000
say "Gap Index of gap Starting Niven"
for (var (n=1, index=0, gap=0, prev=1); index <= threshold; ++n) {
n.is_div(n.digits_sum) || next
if ((var diff = (n - prev)) > gap) {
gap = diff
printf("%3d %15s %15s\n", gap, index, prev)
}
prev = n
++index
}
- 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 2889 32 716 3784 36 1118 6480 44 2948 19872 45 4194 28971 54 5439 38772 60 33494 297864 66 51544 478764 72 61588 589860 88 94748 989867 90 265336 2879865 99 800054 9898956 108 3750017 49989744 126 6292149 88996914
Wren
Limited to Niven numbers up to 1 billion in order to finish in a reasonable time (a little under 2 minutes on my machine).
import "./fmt" for Fmt
var newSum // recursive
newSum = Fn.new {
var ms // also recursive
ms = Fn.new {
ms = newSum.call()
return ms.call()
}
var msd = 0
var d = 0
return Fn.new {
if (d < 9) {
d = d + 1
} else {
d = 0
msd = ms.call()
}
return msd + d
}
}
var newHarshard = Fn.new {
var i = 0
var sum = newSum.call()
return Fn.new {
i = i + 1
while (i%sum.call() != 0) i = i + 1
return i
}
}
System.print("Gap Index of gap Starting Niven")
System.print("=== ============= ==============")
var h = newHarshard.call()
var pg = 0 // previous highest gap
var pn = h.call() // previous Niven number
var i = 1
var n = h.call()
while (n <= 1e9) {
var g = n - pn
if (g > pg) {
Fmt.print("$3d $,13d $,14d", g, i, pn)
pg = g
}
pn = n
i = i + 1
n = h.call()
}
- 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
x86-64 Assembly
This program runs under Linux.
bits 64
section .data
;;; Header
header: db 'Gap no Gap Niven index Niven number',10
db '------ --- ------------- --------------',10
.len: equ $-header
;;; Placeholder for line output
line: db 'XXXXXX'
.gapno: db ' XXX'
.gap: db ' XXXXXXXXXXXXX'
.nivno: db ' XXXXXXXXXXXXXX'
.niv: db 10
.len: equ $-line
section .text
global _start
_start: xor r8,r8 ; Keep a 10 in R8 to divide by
mov r8b,10
mov rsi,header ; Write header
mov rdx,header.len
call write
xor r15,r15 ; Let R15 be the previous number
inc r15
xor r14,r14 ; Let R14 be the gap
xor r13,r13 ; Let R13 be the digit sum
xor r12,r12 ; Let R12 be the index
mov r11,r15 ; Let R11 be the gap index
xor r10,r10 ; And let R10 be the Niven number
jmp niven ; Jump over end of loop
next: mov r15,r10 ; Previous number is now current number
inc r12 ; Increment index
niven: inc r10 ; Check next Niven number
inc r13 ; Calculate next digit sum
mov rax,r10 ; rax = n/10
xor rdx,rdx ; rdx = n%10
digsum: div r8
sub r13,9 ; sum -= 9
test rdx,rdx ; was it divisible by 10?
jnz check ; if not, we're done
test rax,rax ; otherwise, have we reached 0?
jnz digsum ; if not, keep going
check: add r13,9 ; add 9 back
test r13b,1 ; sum divisible by 2?
jnz chdiv ; if not try division
test r10b,1 ; number divisible by 2?
jnz niven
chdiv: mov rax,r10 ; number divisible by sum?
xor rdx,rdx
div r13
test rdx,rdx
jnz niven ; if not, try next number
mov rax,r10 ; calculate gap size
sub rax,r15
cmp rax,r14 ; bigger than previous gap?
jbe next ; If not, count but don't display
mov r14,rax ; If so, store new gap size
mov rbx,line.niv ; Format Niven number
mov rax,r15
mov cl,14
call format
dec rbx
dec rbx
mov rax,r12 ; Niven index
mov cl,13
call format
dec rbx
dec rbx
mov rax,r14 ; Gap
mov cl,3
call format
dec rbx
dec rbx
mov rax,r11 ; Gap index
mov cl,6
call format
mov rsi,rbx ; Write line
mov rdx,line.len
call write
inc r11 ; Increment gap index
cmp r11b,32 ; Done?
jbe next ; If not, next number
mov rax,60
xor rdi,rdi ; Otherwise, exit
syscall
;;; Write RDX chars to STDOUT starting at RSI
write: xor rax,rax ; Write syscall is 1
inc rax
mov rdi,rax ; STDOUT is also 1
push r11 ; R11 is clobbered, keep it
syscall
pop r11
ret
;;; Format number in RAX as ASCII, with thousand
;;; separators; storing at RBX going leftward,
;;; padding with spaces for length CL.
format: mov ch,3 ; Thousands counter
.loop: xor rdx,rdx ; Divide
div r8
add dl,'0' ; ASCII zero
dec rbx ; Store value
mov [rbx],dl
dec cl ; One fewer char left
jz .out ; Stop if field full
test rax,rax ; Done whole number?
jz .ndone
dec ch ; Time for separator?
jnz .loop ; If not, continue;
mov ch,3 ; If so, reset counter,
dec rbx ; Add separator,
mov [rbx],byte ','
dec cl ; One fewer char left
jmp .loop
.ndone: mov al,' ' ; Pad with spaces
test cl,cl ; Done yet?
jz .out
.pad: dec rbx ; If not, add space
mov [rbx],al
dec cl
jnz .pad
.out: ret
- Output:
Gap no Gap Niven index Niven number ------ --- ------------- -------------- 1 1 1 1 2 2 10 10 3 6 11 12 4 7 26 63 5 8 28 72 6 10 32 90 7 12 83 288 8 14 102 378 9 18 143 558 10 23 561 2,889 11 32 716 3,784 12 36 1,118 6,480 13 44 2,948 19,872 14 45 4,194 28,971 15 54 5,439 38,772 16 60 33,494 297,864 17 66 51,544 478,764 18 72 61,588 589,860 19 88 94,748 989,867 20 90 265,336 2,879,865 21 99 800,054 9,898,956 22 108 3,750,017 49,989,744 23 126 6,292,149 88,996,914 24 135 44,194,186 689,988,915 25 144 55,065,654 879,987,906 26 150 61,074,615 989,888,823 27 153 179,838,772 2,998,895,823 28 192 399,977,785 6,998,899,824 29 201 497,993,710 8,889,999,624 30 234 502,602,764 8,988,988,866 31 258 547,594,831 9,879,997,824 32 276 1,039,028,518 18,879,988,824
XPL0
func DigitSum(N, Sum); \Return sum of digits in N given sum of digits in N-1
int N, Sum;
[Sum:= Sum+1;
while N > 0 and rem(N/10) = 0 do
[Sum:= Sum -9;
N:= N/10;
];
return Sum;
];
int Previous, Gap, S, NivenIndex, GapIndex, Niven;
def Tab = 9;
[Previous:= 1;
Gap:= 0;
S:= 0;
NivenIndex:= 0;
GapIndex:= 1;
Text(0, "Index Gap Index Niven^m^j");
Niven:= 1;
while GapIndex <= 23 do
[S:= DigitSum(Niven, S);
if rem(Niven/S) = 0 then
[if Niven > Previous + Gap then
[Gap:= Niven - Previous;
IntOut(0, GapIndex); ChOut(0, Tab);
IntOut(0, Gap); ChOut(0, Tab);
IntOut(0, NivenIndex); ChOut(0, Tab);
IntOut(0, Previous); CrLf(0);
GapIndex:= GapIndex+1;
];
Previous:= Niven;
NivenIndex:= NivenIndex+1;
];
Niven:= Niven+1;
];
]
- Output:
Index Gap Index Niven 1 1 1 1 2 2 10 10 3 6 11 12 4 7 26 63 5 8 28 72 6 10 32 90 7 12 83 288 8 14 102 378 9 18 143 558 10 23 561 2889 11 32 716 3784 12 36 1118 6480 13 44 2948 19872 14 45 4194 28971 15 54 5439 38772 16 60 33494 297864 17 66 51544 478764 18 72 61588 589860 19 88 94748 989867 20 90 265336 2879865 21 99 800054 9898956 22 108 3750017 49989744 23 126 6292149 88996914
Yabasic
sub digit_sum(n, sum)
// devuelve la suma de los dígitos de n dada la suma de los dígitos de n - 1
sum = sum + 1
while n > 0 and (mod(n, 10) = 0)
sum = sum - 9
n = int(n / 10)
end while
return sum
end sub
sub divisible(n, d)
if mod(d, 1) = 0 and mod(n, 1) = 1 then return 0 else return (mod(n, d) = 0) : endif
end sub
gap_index = 0
previous = 1
print "Gap index Gap Niven index Niven number"
print "--------- --- ----------- ------------"
for niven = 1 to 100000000
sum = digit_sum(niven,sum)
if divisible(niven, sum) then
if (niven > previous + gap) then
gap_index = gap_index + 1
gap = niven - previous
print gap_index using "#########";
print gap using "###";
print niven_index using "###,###,###";
print previous using "####,###,###"
endif
previous = niven
niven_index = niven_index + 1
endif
next niven
end
- Output:
Igual que la entrada de FreeBASIC.
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)));
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