Self numbers: Difference between revisions

Content added Content deleted

Inline

Revision as of 15:59, 7 October 2020

A number n is a self number if there is no number g such that g + the sum of g's digits = n. So 18 is not a self number because 9+9=18, 43 is not a self number because 35+5+3=43.
The task is:

 Display the first 50 self numbers;
 I believe that the 100000000th self number is 1022727208. You should either confirm or dispute my conjecture.

2^24036583-1 is a Mersenne prime, claimed to also be a self number. Extra credit to anyone proving it.
Wikipedia Self numbers showing some tricks especially for the number above.

F#

<lang fsharp> // Self numbers. Nigel Galloway: October 6th., 2020 let fN g=let rec fG n g=match n/10 with 0->n+g |i->fG i (g+(n%10)) in fG g g let Self=let rec Self n i g=seq{let g=g@([n..i]|>List.map fN) in yield! List.except g [n..i]; yield! Self (n+100) (i+100) (List.filter(fun n->n>i) g)} in Self 0 99 []

Self |> Seq.take 50 |> Seq.iter(printf "%d "); printfn "" printfn "\n%d" (Seq.item 99999999 Self) </lang>

Output:

1 3 5 7 9 20 31 42 53 64 75 86 97 108 110 121 132 143 154 165 176 187 198 209 211 222 233 244 255 266 277 288 299 310 312 323 334 345 356 367 378 389 400 411 413 424 435 446 457 468

1022727208

Go

Low memory

Simple-minded, uses very little memory (no sieve) but slow - over 2.5 minutes. <lang go>package main

import (

   "fmt"
   "time"

)

func sumDigits(n int) int {

   sum := 0
   for n > 0 {
       sum += n % 10
       n /= 10
   }
   return sum

}

func max(x, y int) int {

   if x > y {
       return x
   }
   return y

}

func main() {

   st := time.Now()
   count := 0
   var selfs []int
   i := 1
   pow := 10
   digits := 1
   offset := 9
   lastSelf := 0
   for count < 1e8 {
       isSelf := true
       start := max(i-offset, 0)
       sum := sumDigits(start)
       for j := start; j < i; j++ {
           if j+sum == i {
               isSelf = false
               break
           }
           if (j+1)%10 != 0 {
               sum++
           } else {
               sum = sumDigits(j + 1)
           }
       }
       if isSelf {
           count++
           lastSelf = i
           if count <= 50 {
               selfs = append(selfs, i)
               if count == 50 {
                   fmt.Println("The first 50 self numbers are:")
                   fmt.Println(selfs)
               }
           }
       }
       i++
       if i%pow == 0 {
           pow *= 10
           digits++
           offset = digits * 9
       }
   }
   fmt.Println("\nThe 100 millionth self number is", lastSelf)
   fmt.Println("Took", time.Since(st))

}</lang>

Output:

The first 50 self numbers are:
[1 3 5 7 9 20 31 42 53 64 75 86 97 108 110 121 132 143 154 165 176 187 198 209 211 222 233 244 255 266 277 288 299 310 312 323 334 345 356 367 378 389 400 411 413 424 435 446 457 468]

The 100 millionth self number is 1022727208
Took 2m35.531949399s

Sieve based

Simple sieve, requires a lot of memory but quick - under 3 seconds.

Nested 'for's used rather than a recursive function for extra speed. <lang go>package main

import (

   "fmt"
   "time"

)

func sieve() []bool {

   sv := make([]bool, 2*1e9+9*9+1)
   n := 0
   for a := 0; a < 2; a++ {
       for b := 0; b < 10; b++ {
           for c := 0; c < 10; c++ {
               for d := 0; d < 10; d++ {
                   for e := 0; e < 10; e++ {
                       for f := 0; f < 10; f++ {
                           for g := 0; g < 10; g++ {
                               for h := 0; h < 10; h++ {
                                   for i := 0; i < 10; i++ {
                                       for j := 0; j < 10; j++ {
                                           sv[a+b+c+d+e+f+g+h+i+j+n] = true
                                           n++
                                       }
                                   }
                               }
                           }
                       }
                   }
               }
           }
       }
   }
   return sv

}

func main() {

   st := time.Now()
   sv := sieve()
   count := 0
   fmt.Println("The first 50 self numbers are:")
   for i := 0; i < len(sv); i++ {
       if !sv[i] {
           count++
           if count <= 50 {
               fmt.Printf("%d ", i)
           }
           if count == 1e8 {
               fmt.Println("\n\nThe 100 millionth self number is", i)
               break
           }
       }
   }
   fmt.Println("Took", time.Since(st))

}</lang>

Output:

The first 50 self numbers are:
1 3 5 7 9 20 31 42 53 64 75 86 97 108 110 121 132 143 154 165 176 187 198 209 211 222 233 244 255 266 277 288 299 310 312 323 334 345 356 367 378 389 400 411 413 424 435 446 457 468 

The 100 millionth self number is 1022727208
Took 2.647602109s

Julia

The code first bootstraps a sliding window of size 81 and then uses this as a sieve. Note that 81 is the window size because the sum of digits of 999,999,999 (the largest digit sum of a counting number less than 1022727208) is 81. <lang julia>gsum(i) = sum(digits(i)) + i isnonself(i) = any(x -> gsum(x) == i, i-1:-1:i-max(1, ndigits(i)*9)) const last81 = filter(isnonself, 1:5000)[1:81]

function checkselfnumbers()

   i, selfcount = 1, 0
   while selfcount <= 100_000_000 && i <= 1022727208
       if !(i in last81)
           selfcount += 1
           if selfcount < 51
               print(i, " ")
           elseif selfcount == 51
               println()
           elseif selfcount == 100_000_000
               println(i == 1022727208 ?
                   "Yes, $i is the 100,000,000th self number." :
                   "No, instead $i is the 100,000,000th self number.")
           end
       end
       popfirst!(last81)
       push!(last81, gsum(i))
       i += 1
   end

end

checkselfnumbers()

</lang>

Output:

1 3 5 7 9 20 31 42 53 64 75 86 97 108 110 121 132 143 154 165 176 187 198 209 211 222 233 244 255 266 277 288 299 310 312 323 334 345 356 367 378 389 400 411 413 424 435 446 457 468
Yes, 1022727208 is the 100,000,000th self number.

Pascal

Works with: Free Pascal

Just "sieving" with only one follower of every number

Translation of: Go

Extended to 10.23e9 <lang pascal>program selfnumb; {$IFDEF FPC}

 {$MODE Delphi}
 {$Optimization ON,ALL}

{$IFEND} {$IFDEF DELPHI} {$APPTYPE CONSOLE} {$IFEND} uses

 sysutils;

const

 MAXCOUNT =103*10000*10000+11*9+ 1;

type

 tDigitSum9999 = array[0..9999] of Uint8;
 tpDigitSum9999 = ^tDigitSum9999;

var

 DigitSum9999 : tDigitSum9999;
 sieve : array of boolean;

procedure dosieve; var

 pSieve : pBoolean;
 pDigitSum :tpDigitSum9999;
 n,c,b,a,s : NativeInt;

Begin

 pSieve := @sieve[0];
 pDigitSum := @DigitSum9999[0];
 n := 0;
 for a := 0 to 102 do
   for b := 0 to 9999 do
   Begin
     s := pDigitSum^[a]+pDigitSum^[b]+n;
     for c := 0 to 9999 do
     Begin
       pSieve[pDigitSum^[c]+s] := true;
       s+=1;
     end;
     inc(n,10000);
   end;

end;

procedure InitDigitSum; var

 i,d,c,b,a : NativeInt;

begin

 i := 9999;
 for a := 9 downto 0 do
   for b := 9 downto 0 do
     for c := 9 downto 0 do
       for d := 9 downto 0 do
       Begin
         DigitSum9999[i] := a+b+c+d;
         dec(i);
       end;

end;

procedure OutPut(cnt,i:NativeUint); Begin

 writeln(cnt:10,i:12);

end;

var

 pSieve : pboolean;
 T0 : Uint64;
 i,cnt,limit,One: NativeUInt;

BEGIN

 setlength(sieve,MAXCOUNT);
 pSieve := @sieve[0];
 T0 := GetTickCount64;
 InitDigitSum;
 dosieve;
 writeln('Sievetime : ',(GetTickCount64-T0 )/1000:8:3,' sec');
 //find first 50
 cnt := 0;
 for i := 0 to MAXCOUNT do
 Begin
   if NOT(pSieve[i]) then
   Begin
     inc(cnt);
     if cnt <= 50 then
       write(i:4)
     else
       BREAK;
   end;
 end;
 writeln;
 One := 1;
 limit := One;
 cnt := 0;
 for i := 0 to MAXCOUNT do
 Begin
   inc(cnt,One-Ord(pSieve[i]));
   if cnt = limit then
   Begin
     OutPut(cnt,i);
     limit := limit*10;
   end;
 end;

END.</lang>

Output:

 time ./selfnumb
Sievetime :    6.579 sec
   1   3   5   7   9  20  31  42  53  64  75  86  97 108 110 121 132 143 154 165 176 187 198 209 211 222 233 244 255 266 277 288 299 310 312 323 334 345 356 367 378 389 400 411 413 424 435 446 457 468
         1           1
        10          64
       100         973
      1000       10188
     10000      102225
    100000     1022675
   1000000    10227221
  10000000   102272662
 100000000  1022727208
1000000000 10227272649

real  0m13,252s

Wren

Translation of: Go

Just the sieve based version as the low memory version would take too long to run in Wren.

Note that you need a lot of memory to run this as Bools in Wren require 8 bytes of storage compared to 1 byte in Go.

Unsurprisingly, very slow compared to the Go version as Wren is interpreted and uses floating point arithmetic for all numerical work. <lang ecmascript>var sieve = Fn.new {

   var sv = List.filled(2*1e9+9*9+1, false)
   var n = 0
   for (a in 0..1) {
       for (b in 0..9) {
           for (c in 0..9) {
               for (d in 0..9) {                    
                  for (e in 0..9) {
                       for (f in 0..9) {                           
                           for (g in 0..9) {
                               for (h in 0..9) {
                                   for (i in 0..9) {
                                       for (j in 0..9) {                                           
                                          sv[a + b + c + d + e + f + g + h + i + j + n] = true
                                          n = n + 1
                                       }
                                   }                                    
                               }
                           }  
                       }
                   }
               }
           }
       }
   }
   return sv

}

var st = System.clock var sv = sieve.call() var count = 0 System.print("The first 50 self numbers are:") for (i in 0...sv.count) {

   if (!sv[i]) {
       count = count + 1
       if (count <= 50) System.write("%(i) ")
       if (count == 1e8) {
           System.print("\n\nThe 100 millionth self number is %(i)")
           break
       }
   }

} System.print("Took %(System.clock-st) seconds.")</lang>

Output:

The first 50 self numbers are:
1 3 5 7 9 20 31 42 53 64 75 86 97 108 110 121 132 143 154 165 176 187 198 209 211 222 233 244 255 266 277 288 299 310 312 323 334 345 356 367 378 389 400 411 413 424 435 446 457 468 

The 100 millionth self number is 1022727208
Took 314.869302 seconds.