When is A111075(n) Odd?

[Max]

Paul D. Hanna wrote:
> Seqfans,
>        In case someone has already extended Leroy's sequence A111075,
> I would like to make an observation here regarding:
> http://www.research.att.com/projects/OEIS?Anum=A111075
> 1,2,3,7,6,21,14,50
> Name: F(n) * sum{k|n} 1/F(k), where F(k) is the kth Fibonacci number.
>  
> Here are more terms:
> 1,2,3,7,6,21,14,50,52,122,90,427,234,784,1038,2351,1598,
> 6860,4182,17262,17262,35622,28658,139703,90031,243308,
> 300405,766850,514230,2367006,1346270,5188658,5326470,
> 11409346,11782764,44717548,24157818,78185688,95140422,
> (PARI) a(n)=fibonacci(n)*sumdiv(n,d,1/fibonacci(d))
>  
> The question that came to mind was: "when is A111075(n) odd?"
> This gives a new sequence:
> "n for which  A111075(n) is odd"
> 1,3,4,6,12,16,24,25,27,48,49,54,64,75,96,100,108,121,147,
> 150,169,192,196,216,243,256,289,294,300,361,363,384,400,432,
> 484,486,507,529,588,600,625,675,676,726,768,784,841,864,867,
> 961,972,1014,1024,1083,1156,1176,1200,1225,1323,1350,1369,
>  
> Conjecture: A111075(n) is odd whenever:
> (i)  n = m^2 for all m>=1 such that 3 does not divide m, and
> (ii)  n = 3*A028982(m) for all m>=1.
> Note that A028982 lists positive integers having an odd sum of divisors.
>  
> Can anyone support this conjecture?  Is this a trivial observation?

The conjecture is true except that (ii) should be
(ii) n = 3^s*A028982(m) for all m>=1 and _odd_ s>=1.

Recall that F(k) divides F(n) as soon as k divides n. Therefore,
A111075(n) = F(n) * sum{k|n} 1/F(k) = sum{k|n} F(n)/F(k)
is a sum of integers.

Calim 1. F(m) is even iff m is a multiple of 3.
Proof trivial.

Claim 2. ord2(F(3^s*t))=ord2(F(3*t)),
where ord2(m) is the maximum power of 2 dividing m.
Proof. Follows from the identity
F(3m) = 5*F(m)^3 + (-1)^m*3*F(m) = (5*F(m)^2 + (-1)^m*3) * F(m).

Claim 3. F(3t)/F(3k) mod 2 = (t/k) mod 2
Proof. Follows from the identity
F(3t) = F(3k)*F(3(t-k)+1) + F(3(t-k))*F(3k-1)


Now let n=3^s*t where 3 does not divide t. Then
A111075(n) mod 2 = [sum{k|n, 3|k} F(n)/F(k) + sum{k|n, 3\not|k} F(n)/F(k)] mod 2

First sum is
sum{r=1..s, k|t} F(n)/F(3^r*k) mod 2
= sum{r=1..s, k|t} F(3t)/F(3k) mod 2
= [s*sum{k|t} F(3t)/F(3k)] mod 2
= [s*sum{k|t} t/k] mod 2
= [s*sigma(t)] mod 2
Second sum is
sum{k|t} F(n)/F(k) mod 2 = [F(n)*numdiv(t)] mod 2

If s=0, then
A111075(n) mod 2 = numdiv(t) mod 2 = numdiv(n) mod 2
is odd iff numdiv(n) is odd implying n is a square.

If s>0, then
A111075(n) mod 2 = [s*sigma(t)] mod 2
is odd iff both s and sigma(t) are odd (implying t \in A028982).

Max