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.
Pascal
Just "sieving" with followers of the selfnumbers up to the limit. <lang pascal> program selfnumbers; {$IFDEF FPC}
{$MODE Delphi}
{$Optimization ON,ALL}
{$IFEND} {$IFDEF DELPHI} {$APPTYPE CONSOLE} {$IFEND} const
BASE = 10;
type
tNumber = record
digits : array[0..23] of byte;
value,
dgtCount,
sumDigit :NativeUint;
end;
tpNumber = ^tNumber;
var
Sieve : array[0..(1022727208 DIV 32 +1)*32] of byte;//1022727208 DgtSumNumbers: array[0..19*9] of tNumber;
procedure NewNumber(n: NativeUint;var number:tNumber); //convert Number into digits and sum of digits var
i,r,d : NativeUint;
Begin
i := 0; number.sumDigit := 0; number.value := n; repeat r := n DIV BASE; d := n-BASE*r; number.digits[i] := d; inc(number.sumDigit,d); n:= r; inc(i); until n = 0; number.dgtCount := i;
end;
procedure NextNumber(var number:tNumber); //add sumofdigits to number -> number var
pDigitSum : tpNumber; i,c,d,sum : NativeUint;
Begin
with number do Begin pDigitSum := @DgtSumNumbers[sumDigit]; value:= value+sumDigit; end;
i := 0;
sum := 0;
c := 0;
repeat
d := number.digits[i]+pDigitSum^.digits[i]+c;
c := 0;
if d >= base then
Begin
d -= BASE;
c := 1;
end;
number.digits[i] := d;
sum += d;
inc(i);
until i = number.dgtCount;
If c > 0 then Begin number.digits[i] := 1; inc(sum); inc(number.dgtCount) end; number.sumDigit := sum;
end;
var
number: tNumber; StartNum,actNum,cnt: NativeUint;
begin
for actNum := 1 to High(DgtSumNumbers) do NewNumber(actNum,DgtSumNumbers[actNum]);
StartNum := 0;
cnt := 0;
repeat
//search next selfnumber
While Startnum<High(Sieve) do
begin
inc(Startnum);
if Sieve[Startnum] = 0 then
Break;
end;
inc(cnt);
If Startnum >=High(Sieve) then
Halt(-253);
If cnt <51 then
write(Startnum,' ');
IF cnt = 100*1000*1000 then
Begin
writeln;
writeln(cnt:10,Startnum:15);
BREAK;
end;
NewNumber(StartNum,number); NextNumber(number); actNum := number.value;
// mark not selfnumbers
while actNum <= High(Sieve) do
Begin
IF Sieve[actNum] = 0 then
Sieve[actNum]:= 1
else
BREAK;
NextNumber(number);
actNum := number.value;
end;
until false;
writeln('finished');
end.</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 100000000 1022727208 finished
real 0m18,764s