# Prime Factors and A100737

Paul D. Hanna pauldhanna at juno.com
Sat Dec 25 19:30:22 CET 2004

```OK, here is the nice, key factor property of sequence A100737
that explains the prime factor behavior observed in prior email:
--------------------------------------------------------------
Each term a(n) is the product of terms a(2^k) for k=0,1,2,...,m,
m=[log_2(n)],
put to the power of the k-th bit in the binary expansion of n:

a(n) = a(2^0)^b(n,0) * a(2^1)^b(n,1) * a(2^2)^b(n,2) *...* a(2^m)^b(n,m)

where b(n,k) = k-th bit in binary(n).
--------------------------------------------------------------

Since a(2^n) = (2^1+1)*(2^2+1)*(2^4+1)*...*(2^(2^n)+1),
as in: a(2^3)=3*5*17*257,  a(2^4)=3*5*17*257*65537, etc.,
then we get the factor behavior observed at the bottom of the attached
prior email.

As empirical evidence of the above factor property,
these PARI programs produce the same sequence A100737,
a(n) using above factor formula, and
b(n) using the inverse modulo 2 binomial transform of 4^n:

a(n)=prod(k=0,length(binary(n))-1,prod(j=0,k,2^(2^j)+1)^bittest(n,k))

b(n)=sum(k=0,n,(-1)^subst(Pol(binary(n-k)),x,1)*(binomial(n,k)%2)*4^k)

The other "inverse modulo 2 binomial transform" of b^n (ex.
A100735-A100741)
sequences all have similar fascinating factor properties.

Merry Christmas,
Paul
---------------------------------------------------------------------
On Thu, 23 Dec 2004 20:45:18 -0500 "Paul D. Hanna" <pauldhanna at juno.com>
writes:
> Paul Barry has some interesting sequences involving the
> "inverse modulo 2 binomial transform" of b^n:  A100735-A100741.
> These sequences seem to have unusual prime factors.
> In particular, consider the prime factors of A100737 (copied below).
...
> ---------------------------------------------------------------------
> URL: http://www.research.att.com/projects/OEIS?Anum=A100737
> Sequence:
> 1,3,15,45,255,765,3825,11475,65535,196605,983025,2949075,
> 16711425,50134275,250671375,752014125,4294967295,
> 12884901885,64424509425,193273528275,1095216660225,
> 3285649980675,16428249903375,49284749710125
> Name:      Inverse modulo 2 binomial transform of 4^n.
> Formula:   a(n)=sum{k=0..n,
> (-1)^A010060(n-k)*mod(binomial(n,k),2)4^k}.
> ------------------------------------------------------------
> FORMULA.
> The formula for A010060(n) is the number of 1's in binary expansion
> of n
> modulo 2.
> So, the PARI CODE for A100737 is:
>
>
A100737(n)=sum(k=0,n,(-1)^subst(Pol(binary(n-k)),x,1)*(binomial(n,k)%2)*4
> ^k)
>
> EXAMPLE:
> Prime factors of terms shown (n=1..23) are:
>  3^1
>  3^1 * 5^1
>  3^2 * 5^1
>  3^1 * 5^1 * 17^1
>  3^2 * 5^1 * 17^1
>  3^2 * 5^2 * 17^1
>  3^3 * 5^2 * 17^1
>  3^1 * 5^1 * 17^1 * 257^1
>  3^2 * 5^1 * 17^1 * 257^1
>  3^2 * 5^2 * 17^1 * 257^1
>  3^3 * 5^2 * 17^1 * 257^1
>  3^2 * 5^2 * 17^2 * 257^1
>  3^3 * 5^2 * 17^2 * 257^1
>  3^3 * 5^3 * 17^2 * 257^1
>  3^4 * 5^3 * 17^2 * 257^1
>  3^1 * 5^1 * 17^1 * 257^1 * 65537^1
>  3^2 * 5^1 * 17^1 * 257^1 * 65537^1
>  3^2 * 5^2 * 17^1 * 257^1 * 65537^1
>  3^3 * 5^2 * 17^1 * 257^1 * 65537^1
>  3^2 * 5^2 * 17^2 * 257^1 * 65537^1
>  3^3 * 5^2 * 17^2 * 257^1 * 65537^1
>  3^3 * 5^3 * 17^2 * 257^1 * 65537^1
>  3^4 * 5^3 * 17^2 * 257^1 * 65537^1

```