[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 ;
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
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.


Matevž Markovič

More information about the SeqFan mailing list