Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In https://oeis.org/A065069 numbers $n$ such that Fibonacci($n$) is not squarefree, but for all proper divisors $k$ of $n$, Fibonacci($k$) is squarefree, are listed.

OEIS gives a Mathematica program (see link) to calculate these indices. The algorithm used, searches primes $p$ and Fibonacci numbers Fib($k$) such that

$$\text{Fib}(k)\;\text{mod}\,p =0$$

The numbers $p\cdot k$ are candidates to be indices of primitive squareful Fibonacci numbers.

Can anyone explain me the reasonning behind this algorithm? Probably some theorems about Fibonacci numbers I don't know are used.

I am interested in alternative algorithms as well.

share|improve this question
    
Perhaps there is a theorem that says that if a prime $p$ divides $F_k$ then $p^2$ divides $F_{pk}$. –  Gerry Myerson Oct 23 '12 at 0:45

2 Answers 2

up vote 2 down vote accepted

The Wikipedia article on Fibonacci numbers says $$F_{kn+c}=\sum_0^k{k\choose i}F_{c-i}F_n^iF_{n+1}^{k-i}$$ Let $c=0$, and let $k=p$ be prime, so $$F_{pn}=pF_{-1}F_nF_{n+1}^{p-1}+\sum_2^p{p\choose i}F_{-i}F_n^iF_{n+1}^{p-i}$$ Note that the $i=0$ term vanishes because $F_0=0$, and I have separated out the $i=1$ term. If $p\mid F_n$, then $p^2$ divides every term on the right side, so $p^2\mid F_{pn}$.

It seems to me that the question is suggesting that squareful is the negation of squarefree, but this is not the case. E.g., the number $12$ is neither squareful nor squarefree.

share|improve this answer
    
How do you calculate the value of $F_{-i}$ with -i negative? –  wnvl Oct 23 '12 at 13:32
    
OK, it is explained in the wiki page F_{-i}=-(-1)^iF_i –  wnvl Oct 23 '12 at 14:18
    
Apparently there is a difference between squareful and squarefull. 12 is squareful oeis.org/wiki/Squareful_numbers –  wnvl Oct 23 '12 at 14:25
    
I wasn't aware of that usage. With all due respect to whoever came up with it, I think it's a very bad coinage. As for negative subscripts, the basic recursion, $F_{n+1}=F_n+F_{n-1}$ can be made to run backwards, e.g., you can get $F_{-1}$ from $F_1=F_0+F_{-1}$. –  Gerry Myerson Oct 23 '12 at 21:29

okay, till $F_{3n}$, it seems true.

$F_{2n} = 2F_{n-1}F_{n} + F_{n}^{2}$, which is divisible by $2^2$.

$F_{3n} = 3F_{n-1}^{2}F_{n} + 3F_{n}^{2}F_{n-1} + 2F_{n}^{3}$ is also divisible by $3^2$.

There might be an inductive way of proving it.

Salahuddin

share|improve this answer
    
Please don't place unrelated self-promoting links into answers. There's space on your user page where you can put such things. –  joriki Oct 23 '12 at 15:08
1  
ok, will do that. I will discontinue it from now. Removing URL now. –  Salahuddin Oct 23 '12 at 15:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.