Skip to search.
primenumbers · Prime numbers and primality testing

Group Information

  • Members: 944
  • Category: Number Theory
  • Founded: Dec 27, 2000
  • Language: English
? Already a member? Sign in to Yahoo!

Yahoo! Groups Tips

Did you know...
Real people. Real stories. See how Yahoo! Groups impacts members worldwide.

Messages

  Messages Help
Advanced
New sieve and a challenge   Message List  
Reply Message #9173 of 24247 |
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";
}
}


=====
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.

__________________________________________________
Do you Yahoo!?
Faith Hill - Exclusive Performances, Videos & More
http://faith.yahoo.com



Fri Oct 11, 2002 1:17 pm

thefatphil
Offline Offline
Send Email Send Email

Message #9173 of 24247 |
Expand Messages Author Sort by Date

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... ...
Jon Perry
jon_perryuk Offline Send Email
Oct 11, 2002
11:28 am

... 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...
Phil Carmody
thefatphil Offline Send Email
Oct 11, 2002
12:24 pm

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...
Phil Carmody
thefatphil Offline Send Email
Oct 11, 2002
1:17 pm

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...
Jon Perry
jon_perryuk Offline Send Email
Oct 11, 2002
5:11 pm
Advanced

Copyright © 2010 Yahoo! Inc. All rights reserved.
Privacy Policy - Terms of Service - Guidelines NEW - Help