Increasing gaps between consecutive Niven numbers: Difference between revisions

From Rosetta Code
Content added Content deleted
m (→‎{{header|Perl 6}}: better idiom)
(julia example)
Line 133: Line 133:
276 1,039,028,518 18,879,988,824
276 1,039,028,518 18,879,988,824
</pre>
</pre>


=={{header|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>{{out}}
<pre>
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
</pre>



=={{header|Perl 6}}==
=={{header|Perl 6}}==

Revision as of 18:02, 12 January 2020

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

Note:   Niven   numbers are also called   Harshad   numbers.

  They are also called   multidigital   numbers.


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

Evenly divisible   means   divisible with no remainder.


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


Related task


Also see



Go

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

Works with: Rakudo version 2019.11

<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

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)

  1. = 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*/
  1. = 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