[seqfan] Re: Sequences that need b-files

[David Wilson]

I acknowledge your comments on hard sequences.

However, I am a bit skeptical about how helpful theta series or modular 
forms would be helpful in extending A18 et al.

A18 is the number of k <= 2^n of the form p(x, y) = x^2 + 16y^2. The 
straightforward way to compute this function is to run k from 0 to 2^k, 
and on each iteration, determine if k is of the form p(x, y) and count 
it if it is. Since the loop has 2^n+1 iterations, this approach requires 
time exponential in n, regardless of how we decide k is of correct form 
(whether we pre-mark elements of form p(x, y) in an array, or determine 
theta(k) > 0, or use a Bresenham-like algorithm to search out a solution 
to p(x, y) = k).

My point being, knowing how to quickly decide if element k is in a set S 
doesn't give us much purchase in determining how many elements of S are 
on a given range: we still have to effectively iterate through the range 
and count the elements in S. For the specific sequences in question, 
this range is growing exponentially in n, implying exponential 
computation time. I accede that there may be tricks that significantly 
reduce the work, I do not know them, and my feeling was that if such 
tricks were known, we could apply them to the fast computation of, say, 
pi(n) for very large n (hence fast computation of isPrime(n) = pi(n) - 
pi(n-1)).

All this to say, I don't think A18 et al can be computed quickly. I 
would love to be shown wrong.

On 3/25/2012 11:23 AM, Neil Sloane wrote:
> David,  I WILL TYPE MY REPLIES IN CAPS
>
> On Sun, Mar 25, 2012 at 11:00 AM, David Wilson<davidwwilson at comcast.net>wrote:
>
>> Sequences 18, 21, 24, 49, 50, 67, 72, 74, 75, 76 and 77 (and other
>> sequences beyond the 1-100 range) are of the form
>>
>>     Number of positive integers<= 2^n of form p(x, y)
>>
>> where p(x, y) is a quadratic polynomial (e.g. x^2 + y^2, x^2 + xy + y^2).
>> I extended a few of these sequences myself (most anonymously) to full STU
>> length some time ago. I observe that these sequences are difficult to
>> compute (they have the aroma of prime-counting sequences), leastwise, I was
>> unable to find any significant shortcuts (not that I am a brilliant number
>> theorist). I doubt you are going to get b-file worthy extensions of these
>> sequences, indeed, you might consider adding the "hard" keyword.
>>
> HARD IS SUPPOSED TO MEAN REALLY REALLY HARD, that the
> next term is almost beyond reach. I don't think these are that hard.
> You can compute them using theta series and/or modular forms.
>