[seqfan] Re: Comment about A002822
alois.heinz at hs-heilbronn.de
Fri May 24 17:22:07 CEST 2019
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.
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.
> 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,
>> 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.
>>> -- Nando
>>> Seqfan Mailing list - http://list.seqfan.eu/
>> Seqfan Mailing list - http://list.seqfan.eu/
> Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan