Increasing gaps between consecutive Niven numbers: Difference between revisions
Added Wren |
m →{{header|Wren}}: Minor correction to preamble. |
||
Line 1,018: | Line 1,018: | ||
{{trans|Go}} |
{{trans|Go}} |
||
{{libheader|fmt}} |
{{libheader|fmt}} |
||
Limited to Niven numbers |
Limited to Niven numbers up to 1 billion in order to finish in a reasonable time (a little under 2 minutes on my machine). |
||
<lang ecmascript>import "/fmt" for Fmt |
<lang ecmascript>import "/fmt" for Fmt |
||
Revision as of 09:48, 12 May 2020
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
C
<lang 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, int 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; int niven_index = 0, gap_index = 1, sum = 0;
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;
}</lang>
- 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++
<lang cpp>#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, int 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; int niven_index = 0, gap_index = 1, sum = 0;
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;
}</lang>
- 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
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
Haskell
<lang 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"</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
J
<lang 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 </lang>
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. <lang J>( ~. ( >./\ ( 2 -~/\ A ) ) )</lang>
Given that <lang J>A</lang> 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
<lang 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; }
} </lang>
- 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
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
Pascal
As fast as GO <lang pascal>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.</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 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
<lang 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;
}</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)
Raku
(formerly 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
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= 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
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). <lang ecmascript>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) { System.print("%(Fmt.d(3, g)) %(Fmt.dc(13, i)) %(Fmt.dc(14, pn))") pg = g } pn = n i = i + 1 n = h.call()
}</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
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