[seqfan] Re: A122036

[Matevž Markovič]

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č