Sequences that pass recursion test, but ...

[Max Alekseyev]

On 3/2/07, Tanya Khovanova <tanyakh at tanyakhovanova.com> wrote:

> Here are some of these sequences:
> A078642 a(n) = a(n-1)+a(n-2), a(0) = 4, a(1) = 6. Numbers with two representations as the sum of two Fibonacci numbers.

This follows the conjecture listed in the description of A078642.
Actually, the conjecture has a simple proof:

Suppose that the number m has exactly two representations as the sum
of two Fibonacci  numbers. There are three types of representations
possible:
(I) the sum of two equal Fibonacci numbers
(II) the sum of two consecutive Fibonacci numbers
(III) the sum of two distinct non-consecutive Fibonacci numbers

Lemma. The two representations of m>2 must be of different types.
Proof.
Two representations of m>2 both of type (I) are not possible as 2*F_n
is a strictly increasing function for n>=2.
Similarly, two representations of m both of type (II) are not possible
as F_n + F_{n+1} is a strictly increasing function for n>=0.
Finally, two representations of m both of type (III) are not possible
as that would violate the property of the Fibonacci numeral system
(the uniqueness of representation of all non-negative integers).

Now, consider all possible pairs of representation types:

(I) and (II) are possible only for m=2:
2 = 2*F_1 = 2*F_2 = F_1+F_2
but m=2 has more than two different representations.

(II) and (III) are not possible together as that would again violate
the property of the Fibonacci numeral system.

Finally, (I) and (III) gives rise to the sequence of
a(n) = 2 * F_n = F_{n+1} + F_{n-1}

So, the "conjecture" in A078642 should be turned into the "statement",
and Tanya's formula can be added to the description.

> A081808 a(n) = 2*a(n-1), a(0) = 12. Numbers n such that the largest prime power in n factorization equals phi(n).

Let n=p^k*q where p^k is the largest prime power is the factorization
of n and (p,q)=1.
If n belongs to A081808 then
p^k = phi(n) = (p-1)*p^(k-1)*phi(q),
implying that p=2 (since p-1 cannot divide p^k for prime p>2). Then
2 = phi(q),
implying that q=3.
Therefore, A081808 is simply the sequence of 3*2^n for n=2,3,...
Besides two missing terms, it coincides with A007283.
Tanya's formula does hold again.

> A044322 a(n) = a(n-1) + 81, a(0) = 71. Numbers n such that string 7,8 occurs in the base 9 representation of n but not of n-1.

The sequence A044322 does NOT satisfy the recurrent formula.
A counterexample is 5822 which belongs to the sequence satisfying the
recurrent formula above (for n=71) but does NOT belong to A044322.

> A088475 a(n) = a(n-1) + 1, a(0) = 10. Numbers n such that dismal sum of prime divisors of n is ≥ n.

Something wrong with A088475. Why 10 is an element of A088475?
10 has two prime divisors: 2 and 5. Their dismal sum is 5 (according
to the definition given in A087061) which is less than 10. What's
wrong?

btw, I think dismal-related sequences are missing the "base" keyword
as the dismal operation are defined via decimal representations of the
operands.

Max



Max,

This is beautiful!
Except I do not know what dismal is :-(

Did you submit your comments to OEIS?

Tanya

---------- Original Message ----------------------------------

>On 3/2/07, Tanya Khovanova <tanyakh at tanyakhovanova.com> wrote:
>
>> Here are some of these sequences:
>> A078642 a(n) = a(n-1)+a(n-2), a(0) = 4, a(1) = 6. Numbers with two representations as the sum of two Fibonacci numbers.
>
>This follows the conjecture listed in the description of A078642.
>Actually, the conjecture has a simple proof:
>
>Suppose that the number m has exactly two representations as the sum
>of two Fibonacci  numbers. There are three types of representations
>possible:
>(I) the sum of two equal Fibonacci numbers
>(II) the sum of two consecutive Fibonacci numbers
>(III) the sum of two distinct non-consecutive Fibonacci numbers
>
>Lemma. The two representations of m>2 must be of different types.
>Proof.
>Two representations of m>2 both of type (I) are not possible as 2*F_n
>is a strictly increasing function for n>=2.
>Similarly, two representations of m both of type (II) are not possible
>as F_n + F_{n+1} is a strictly increasing function for n>=0.
>Finally, two representations of m both of type (III) are not possible
>as that would violate the property of the Fibonacci numeral system
>(the uniqueness of representation of all non-negative integers).
>
>Now, consider all possible pairs of representation types:
>
>(I) and (II) are possible only for m=2:
>2 = 2*F_1 = 2*F_2 = F_1+F_2
>but m=2 has more than two different representations.
>
>(II) and (III) are not possible together as that would again violate
>the property of the Fibonacci numeral system.
>
>Finally, (I) and (III) gives rise to the sequence of
>a(n) = 2 * F_n = F_{n+1} + F_{n-1}
>
>So, the "conjecture" in A078642 should be turned into the "statement",
>and Tanya's formula can be added to the description.
>
>> A081808 a(n) = 2*a(n-1), a(0) = 12. Numbers n such that the largest prime power in n factorization equals phi(n).
>
>Let n=p^k*q where p^k is the largest prime power is the factorization
>of n and (p,q)=1.
>If n belongs to A081808 then
>p^k = phi(n) = (p-1)*p^(k-1)*phi(q),
>implying that p=2 (since p-1 cannot divide p^k for prime p>2). Then
>2 = phi(q),
>implying that q=3.
>Therefore, A081808 is simply the sequence of 3*2^n for n=2,3,...
>Besides two missing terms, it coincides with A007283.
>Tanya's formula does hold again.
>
>> A044322 a(n) = a(n-1) + 81, a(0) = 71. Numbers n such that string 7,8 occurs in the base 9 representation of n but not of n-1.
>
>The sequence A044322 does NOT satisfy the recurrent formula.
>A counterexample is 5822 which belongs to the sequence satisfying the
>recurrent formula above (for n=71) but does NOT belong to A044322.
>
>> A088475 a(n) = a(n-1) + 1, a(0) = 10. Numbers n such that dismal sum of prime divisors of n is ≥ n.
>
>Something wrong with A088475. Why 10 is an element of A088475?
>10 has two prime divisors: 2 and 5. Their dismal sum is 5 (according
>to the definition given in A087061) which is less than 10. What's
>wrong?
>
>btw, I think dismal-related sequences are missing the "base" keyword
>as the dismal operation are defined via decimal representations of the
>operands.
>
>Max
>


_________________________________________________________________
Need personalized email and website? Look no further. It's easy
with Doteasy $0 Web Hosting! Learn more at www.doteasy.com