[seqfan] Re: A122036
Matevž Markovič
matevz.markovic.v at gmail.com
Mon Mar 28 11:27:50 CEST 2011
Mr. Franklin T. wrote "Looking at the sequence, it appears that this has
been tested only up to 10^7. By contrast, the related question in A006037 is
documented as tested up to 10^17."
As far as I am concerned, there is no way for anyone alone to compute this
sequence up to much more than 10^7!
Some numbers bellow 10^7 have >50 divisors, that means that they have more
than 2^50 valid subsets! i.e. 351225 has 35 divisors, that is 2^35 subsets.
I wrote this simple algorithm for checking, if the number a is in A136446:
for(register int_fast64_t j = 0; j<number_of_subsets; j++)
{
//add 1 to the binary number
while(tabela_bitov[i] == 1 && i<number_of_divisors)
{
tabela_bitov[i] = 0 ;
i++;
}
tabela_bitov[i] = 1;
for(i=0; i < number_of_divisors; i++)
{
if(tabela_bitov[i] == 1)
{
sum = sum + divisors[i];
}
}
if(sum == a) //is this number in A136446?
return true;
//the sum of this subset does not equal a, try the next subset!
}
As you see, this algorithm is of the form O(number_of_subsets) or
O(2^number_of_divisors)!
Is there any way I can speed-up my algorithm, so that it will reduce the
number of needed subsets to process?
Anyway, I left it running for 11 hours now... 89 numbers processed so far
(510000 - 510089), while the second CPU is still struggling with 500000.
Yours,
Matevž Markovič
More information about the SeqFan
mailing list