[seqfan] Re: Comment about A002822

[Heinz, Alois]

It is a trivial algorithm that tests all potential divisors.

The running time is exponential in the length of n.

I would not like to see comments like this being added
to all sequences having the word prime in its name.

Best regard,

Alois

Am 24.05.2019 um 16:30 schrieb israel at math.ubc.ca:
> I agree that it is not efficient, but neither is Wilson's theorem.
> That shouldn't disqualify it from being mentioned in a comment.
>
> Cheers,
> Robert
>
> On May 24 2019, Heinz, Alois wrote:
>
>>
>> This is not efficient:
>>
>> See the for-loop "from 1 to k"
>>
>> Please do not add this as a comment.
>>
>> Best regards,
>>
>> Alois
>>
>> Am 24.05.2019 um 11:29 schrieb nando:
>>> Hi SeqFans,
>>>
>>> I know about an algorithm for testing whether an integer n belongs to
>>> the A002822 sequence (Numbers n such that 6n-1, 6n+1 are twin primes).
>>> The interesting part (at least for me) is that this algorithm involves
>>> no primality tests whatsoever.
>>>
>>> For n >= 4
>>> * compute k = floor((1+sqrt(1+6n))/6)
>>> * n is a member of A002822 iff neither (6j-1) nor (6j+1) divide
>>> (n^2-j^2) for all j from 1 to k
>>>
>>> For n < 4, the above k turns out to be 0, so there are no filters and
>>> the test is passed by default.
>>>
>>> I've never seen this algorithm mentioned anywhere, so I'm looking for
>>> feedback from the list subscribers as to whether or not this could
>>> possibly be a worthy addition to the comments of that sequence.
>>>
>>> Thanks.
>>> -- Nando
>>>
>>> -- 
>>> Seqfan Mailing list - http://list.seqfan.eu/
>>
>>
>> -- 
>> Seqfan Mailing list - http://list.seqfan.eu/
>>
>>
>
> -- 
> Seqfan Mailing list - http://list.seqfan.eu/