Self numbers
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.
224036583-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 - around 2 seconds.
Nested 'for's used rather than a recursive function for extra speed.
Have also incorporated Enter your username's suggestion (see Talk page) of using partial sums for each loop which improves performance by about 25%. <lang go>package main
import (
"fmt" "time"
)
func sieve() []bool {
sv := make([]bool, 2*1e9+9*9 + 1) n := 0 var s [8]int for a := 0; a < 2; a++ { for b := 0; b < 10; b++ { s[0] = a + b for c := 0; c < 10; c++ { s[1] = s[0] + c for d := 0; d < 10; d++ { s[2] = s[1] + d for e := 0; e < 10; e++ { s[3] = s[2] + e for f := 0; f < 10; f++ { s[4] = s[3] + f for g := 0; g < 10; g++ { s[5] = s[4] + g for h := 0; h < 10; h++ { s[6] = s[5] + h for i := 0; i < 10; i++ { s[7] = s[6] + i for j := 0; j < 10; j++ { sv[s[7]+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 1.984969034s
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.
Faster version
Contains tweaks peculiar to the "10 to the nth" self number. Timings include compilation times. <lang julia>const MAXCOUNT = 103 * 10000 * 10000 + 11 * 9 + 1
function dosieve!(sieve, digitsum9999)
n = 1 for a in 1:103, b in 1:10000 s = digitsum9999[a] + digitsum9999[b] + n for c in 1:10000 sieve[digitsum9999[c] + s] = true s += 1 end n += 10000 end
end
initdigitsum() = reverse!(vec([sum(k) for k in Iterators.product(9:-1:0, 9:-1:0, 9:-1:0, 9:-1:0)]))
function findselves()
sieve = zeros(Bool, MAXCOUNT+1) println("Sieve time:") @time begin digitsum = initdigitsum() dosieve!(sieve, digitsum) end cnt = 1 for i in 1:MAXCOUNT+1 if !sieve[i] cnt > 50 && break print(i, " ") cnt += 1 end end println() limit, cnt = 1, 0 for i in 0:MAXCOUNT cnt += 1 - sieve[i + 1] if cnt == limit println(lpad(cnt, 10), lpad(i, 12)) limit *= 10 end end
end
@time findselves()
</lang>
- Output:
Sieve time: 7.187635 seconds (2 allocations: 78.203 KiB) 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 16.999383 seconds (42.92 k allocations: 9.595 GiB, 0.01% gc time)
Pascal
Just "sieving" with only one follower of every number
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
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 var s = [0] * 8 for (a in 0..1) { for (b in 0..9) { s[0] = a + b for (c in 0..9) { s[1] = s[0] + c for (d in 0..9) { s[2] = s[1] + d for (e in 0..9) { s[3] = s[2] + e for (f in 0..9) { s[4] = s[3] + f for (g in 0..9) { s[5] = s[4] + g for (h in 0..9) { s[6] = s[5] + h for (i in 0..9) { s[7] = s[6] + i for (j in 0..9) { sv[s[7] + 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 222.789713 seconds.