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 - 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.
Faster version
Contains tweaks peculiar to the "10 to the 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
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.