Prime numbers and primality testing
Yahoo Group

New sieve and a challenge

===============================================
Jon Perry     Message 1 of 4  Oct 11, 2002
-----------------------------------------------
A new and exciting sieve:

Read the integers, and strike out all numbers with a digit sum of n.

i.e. we start with 1, so we cross out 10,100,1000,10000, etc...
then 2, so cross out 11,20,101,110,200,1001,1010,1100,,etc...

and so on.

The sequence starts 1,2,3,4,5,6,7,8,9,19,28

The sequence is boring to begin with, but as more terms are produced, it
becomes less easy to predict if n is in the sequence.

And this is the challenge, produce an algorithm to determine whether n is an
element of S.

-----------------------------

Delphi2 code:

type
TForm1 = class(TForm)
Memo1: TMemo;
Button1: TButton;
procedure Button1Click(Sender: TObject);
private
function sumdigits(x:integer):integer;
public
{ Public declarations }
end;

var
Form1: TForm1;
a:array[0..20000] of integer;
i,j,c,sac:integer;
s,xc:integer;
str,s2:string;
sa:array[0..10000] of string;

implementation

{$R *.DFM}

procedure TForm1.Button1Click(Sender: TObject);
begin
c:=1;
sac:=0;
memo1.lines.add('1');
for i:=1 to 20000 do a[i]:=i;
while c<20001 do begin
for j:=1 to 20000 do if sumdigits(j)=c then a[j]:=0;
a[c]:=0;
while (a[c]=0) and (c<20001) do inc(c);
str:=inttostr(a[c]);
sa[sac]:=str;
memo1.lines.add(sa[sac]);
inc(sac);
end;

end;

function Tform1.sumdigits(x:integer):integer;
begin
xc:=0;
s2:=inttostr(x);
for i:=1 to length(s2) do inc(xc,strtoint(copy(s2,i,1)));
sumdigits:=xc;
end;

end.

-----------------------------

Jon Perry
perry@...
http://www.users.globalnet.co.uk/~perry/maths
BrainBench MVP for HTML and JavaScript
http://www.brainbench.com
===============================================
Phil Carmody     Message 2 of 4  Oct 11, 2002
-----------------------------------------------
--- Jon Perry <perry@...> wrote:
> A new and exciting sieve:
> 
> Read the integers, and strike out all numbers with a digit sum of n.
> 
> i.e. we start with 1, so we cross out 10,100,1000,10000, etc...
> then 2, so cross out 11,20,101,110,200,1001,1010,1100,,etc...
> 
> and so on.
> 
> The sequence starts 1,2,3,4,5,6,7,8,9,19,28
> 
> The sequence is boring to begin with, but as more terms are produced, it
> becomes less easy to predict if n is in the sequence.
> 
> And this is the challenge, produce an algorithm to determine whether n is an
> element of S.

An element n is in S iff its digital sum is not in S.
Recursive, looks like O(ln(n)) steps
e.g.

123, sum = 6 in, so 123 out.
1234, sum = 10, sum = 1 in, so 10 out, so 1234 in.
12345, sum = 15, sum = 6 in, so 15 out, so 12345 in.
123456, sum = 21, sum = 3 in, so 21 out, so 123456 in.
7777, sum = 28, sum = 10, sum = 1 in, so 10 out, so 28 in, so 7777 out

#!/usr/bin/perl -w

sub sumdig { my $sum=0; map { $sum+=int($_); } split(/\D*/,$_[0]); $sum; }

sub sumtest
{   
my $n=pop;
print($n);
if($n>9)
{   
print(', sum = ');
$in=!sumtest(sumdig($n));
print(", so $n", $in?' in':' out');
$in;
}
else
{   
print(' in');
1;
}
}
while(<>)
{   
chomp;
sumtest($_) if($_);
print"\n";
}

=====
First rule of Factor Club - you do not talk about Factor Club.
Second rule of Factor Club - you DO NOT talk about Factor Club.
Third rule of Factor Club - when the cofactor is prime, or you've trial-
divided up to the square root of the number, the factoring is over.

===============================================
Phil Carmody     Message 3 of 4  Oct 11, 2002
-----------------------------------------------
Binary equivalent:

2
10, sum = 1 in, so 10 out
3
11, sum = 10, sum = 1 in, so 10 out, so 11 in
4
100, sum = 1 in, so 100 out
5
101, sum = 10, sum = 1 in, so 10 out, so 101 in
6
110, sum = 10, sum = 1 in, so 10 out, so 110 in
7
111, sum = 11, sum = 10, sum = 1 in, so 10 out, so 11 in, so 111 out
8
1000, sum = 1 in, so 1000 out
9
1001, sum = 10, sum = 1 in, so 10 out, so 1001 in
10
1010, sum = 10, sum = 1 in, so 10 out, so 1010 in
11
1011, sum = 11, sum = 10, sum = 1 in, so 10 out, so 11 in, so 1011 out
12
1100, sum = 10, sum = 1 in, so 10 out, so 1100 in
13
1101, sum = 11, sum = 10, sum = 1 in, so 10 out, so 11 in, so 1101 out
14
1110, sum = 11, sum = 10, sum = 1 in, so 10 out, so 11 in, so 1110 out
15
1111, sum = 100, sum = 1 in, so 100 out, so 1111 in
16
10000, sum = 1 in, so 10000 out

Or the sequence as a whole
1 3 5 6 9 10 12 15 17 18 20 23 24 27 29 30 33 34 36 39 40 43 45 46 48 51 53
54 57 58 60 65 66 68 71 72 75 77 78 80 83 85 86 89 90 92 96 99 ...

Jon, I think these are far more sensible than some of the nonsense on OEIS,
so I'll submit the binary one, refering to your decimal original one, do you
want to submit the decimal one?
I guess that I should do the other bases too...

Anyway, here's the modified binary code:

#!/usr/bin/perl -w

my $print=1;

sub sumbit { my $sum=0; my $v=pop; while($v) { $v&=$v-1; ++$sum } $sum }
sub binarize { my $s=''; my $v=pop; while($v) { $s=($v&1).$s; $v>>=1; } $s }
sub sumtest 
{ 
my $n=pop; 
print(binarize($n)) if($print); 
if($n>1)
{
print(', sum = ') if($print);
$in=!sumtest(sumbit($n));
print(", so ", binarize($n), $in?' in':' out') if($print);
$in;
}
else
{ 
print(' in') if($print);
1;
}
}

if($ARGV[0])
{
$print=0;
for $n (1 .. $ARGV[0]) { if(sumtest($n)) { print "$n " } }
print"\n";
}
else
{
while(<>)
{
chomp;
sumtest($_) if($_);
print"\n";
}
}

===============================================
Jon Perry     Message 4 of 4  Oct 11, 2002
-----------------------------------------------
I'm about to submit the decimal one, but the rest (esp. Hex), are free for
anyone else.

I came up with:

sumdigits(n)=local(c);c=0;while (n>0,c=c+n%10;n=n-n%10;n=n/10);c
checkSieve(n)=local(c);c=0;while(n>9, n=sumdigits(n);c++);1-c%2
for (n=1,200,if (checkSieve(n),print1(n,",")))

i.e. an integer is in S iff it takes an even number of sumdigit steps to
reduce n to a single integer.

Jon Perry
perry@...
http://www.users.globalnet.co.uk/~perry/maths
BrainBench MVP for HTML and JavaScript
http://www.brainbench.com

-----Original Message-----
From: Phil Carmody [mailto:thefatphil@...]
Sent: 11 October 2002 14:17
To: primenumbers
Subject: Re: [PrimeNumbers] New sieve and a challenge

Binary equivalent:

2
10, sum = 1 in, so 10 out
3
11, sum = 10, sum = 1 in, so 10 out, so 11 in
4
100, sum = 1 in, so 100 out
5
101, sum = 10, sum = 1 in, so 10 out, so 101 in
6
110, sum = 10, sum = 1 in, so 10 out, so 110 in
7
111, sum = 11, sum = 10, sum = 1 in, so 10 out, so 11 in, so 111 out
8
1000, sum = 1 in, so 1000 out
9
1001, sum = 10, sum = 1 in, so 10 out, so 1001 in
10
1010, sum = 10, sum = 1 in, so 10 out, so 1010 in
11
1011, sum = 11, sum = 10, sum = 1 in, so 10 out, so 11 in, so 1011 out
12
1100, sum = 10, sum = 1 in, so 10 out, so 1100 in
13
1101, sum = 11, sum = 10, sum = 1 in, so 10 out, so 11 in, so 1101 out
14
1110, sum = 11, sum = 10, sum = 1 in, so 10 out, so 11 in, so 1110 out
15
1111, sum = 100, sum = 1 in, so 100 out, so 1111 in
16
10000, sum = 1 in, so 10000 out

Or the sequence as a whole
1 3 5 6 9 10 12 15 17 18 20 23 24 27 29 30 33 34 36 39 40 43 45 46 48 51 53
54 57 58 60 65 66 68 71 72 75 77 78 80 83 85 86 89 90 92 96 99 ...

Jon, I think these are far more sensible than some of the nonsense on OEIS,
so I'll submit the binary one, refering to your decimal original one, do you
want to submit the decimal one?
I guess that I should do the other bases too...

Anyway, here's the modified binary code:

#!/usr/bin/perl -w

my $print=1;

sub sumbit { my $sum=0; my $v=pop; while($v) { $v&=$v-1; ++$sum } $sum }
sub binarize { my $s=''; my $v=pop; while($v) { $s=($v&1).$s; $v>>=1; } $s }
sub sumtest
{
my $n=pop;
print(binarize($n)) if($print);
if($n>1)
{
print(', sum = ') if($print);
$in=!sumtest(sumbit($n));
print(", so ", binarize($n), $in?' in':' out') if($print);
$in;
}
else
{
print(' in') if($print);
1;
}
}

if($ARGV[0])
{
$print=0;
for $n (1 .. $ARGV[0]) { if(sumtest($n)) { print "$n " } }
print"\n";
}
else
{
while(<>)
{
chomp;
sumtest($_) if($_);
print"\n";
}
}

===============================================
Cached by Georg Fischer at Nov 14 2019 12:47 with clean_yahoo.pl V1.4