# [seqfan] Re: computability of A080075 Proth numbers

Maximilian Hasler maximilian.hasler at gmail.com
Mon Aug 16 16:12:19 CEST 2010

```> Apparently A080075(n)-1 = A116882(n+1); found by Superseeker, checked
> for n  <= 1300. A080075 and A116882 do not crossreference each other.

This is obviously true  :
if N is a Proth number,  the largest odd divisor of N-1  is
k = ( N-1) / 2 ^ valuation( N-1 , 2 )

and  k < 2^m  <=>  k^2 < k*2^m = N-1.

FYI, some minutes before reveiving your message I had just submitted :

%F A080075 a(n) = A157892(n)*2^A157893(n) + 1.
%o A080075 (PARI) isproth(x)={ !bittest(x--,0) & (x>>valuation(x,2))^2 < x }

and this PARI code is just equivalent to
your observation + definition of A116882 with <= replaced by < as to
exclude the first term of A116882 which does not correspond to a Proth
number
(which explains the "offset" +1 in the formula you gave).

Inspired by Georgi Guninski 's observation

> a(n+1) = (-a(n - 1) + 2*a(n))
> OR
> a(n+1) = (-2*a(n - 1) + 3*a(n))

I considered the sequence
b = min( -a[i-1]+2*a[i],  -2*a[i-1]+3*a[i] )

which turns out to be
b[i] = a[i] + 2^m[i]
with
m[2] = 1,
m[3..5] = 2, [3 terms]
m[6..11] = 3 [6 terms],
m[12..23] = 4 [12 terms],
m[24..47] = 5 [24 terms], etc...

Maximilian

> %N A116882 A number n is included if (highest odd divisor of n)^2 <= n.
>
> Georgi Guninski schrieb:
>> A080075 Proth numbers: of the form k*2^m + 1 for k odd, m >= 1 and 2^m >
>> k
>>
>> machine analysis seems to suggest these relations (verified to 10 000
>> against the OEIS bfile)
>>
>> a(2*n-1) = (4*a(n - 1) - 3)
>> a(2*n) = ( 2*a(n - 1) + 2*a(n) - 3 )
>> a(2*n+1) = (4*a(n) - 3)
>>
>> a(n+1) = (-a(n - 1) + 2*a(n))
>>
>> OR (these are the roots of a quadratic relation, a possible approach may
>> be to take the smaller proth of them)
>>
>> a(n+1) = (-2*a(n - 1) + 3*a(n))
>>
>> doubling formulas resemble "divide and conquer sequences" - do proth
>> numbers have generating function ?
>>
>>
>
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>

```