[seqfan] Re: Reciprocal Recaman

[David Wilson]

The computing power we have at our disposal these days is really quite
impressive.

> -----Original Message-----
> From: SeqFan [mailto:seqfan-bounces at list.seqfan.eu] On Behalf Of Don
> Reble
> Sent: Saturday, November 16, 2013 1:05 AM
> To: Sequence Fanatics Discussion list
> Subject: [seqfan] Re: Reciprocal Recaman
> 
> > Did you use integer or double precision arithmetic to get these values?
> 
>     Exact rational arithmetic.
>     For those who want to double-check, my 45984249th sum is
>                        24845...8268199366363305313
>         ------------------------------------------
>         29764123805591054356...9475399680000000000
>     with 19971600 digits elided from each.

The computing power we have at our disposal these days is indeed impressive.

I would expect a(n) to be in the same ballpark with A003418(n), which is in
the same ballpark as exp(n).
Hence I would expect a(n) to have around n/ln(10) digits, specifically
a(45984249) should have about 19970706 digits.
That is consistent with the number of digits you claim, so I believe you
with respect to using exact rational arithmetic.
I don't have the math packages necessary to verify your values, though.

> > Do we know for sure that the denominators are A002805?
> 
> > They differ from a(20) on....
> 
>     Yes, but then they agree at a(28)-a(32), a(55)-a(64), a(88)-a(90),
>     a(125)-a(142), ...

Out of curiosity, how often do A002805 and A231693 agree with A003418?

> > I believe that all the terms of the reciprocal Recaman are distinct...
> 
>     Me, too. Consider any harmonic sum
>         S = +- 1/(a+1) +- 1/(a+2) +- 1/(a+3) +- ... +- 1/(a+n).
>     where one puts any sign on any term, and there is at least one term.
>     Let G be the g.c.d. of the denominator(s). Then for any denominator
>     D, G/D is an integer, and G*S = sum(+- G/D_i) is an integer.
> 
>     Let E be the highest power of two which divides G. Then there is
>     only one multiple of E among the denominators. (If there were two,
>     they would be consecutive multiples of E, and one would be divisible
>     by 2*E.) Call that denominator F.
> 
>     So (+- G/F) is an odd integer, and for all other denominators D,
>     (+- G/D) is an even integer. Therefore G*S is odd, not zero, and S
>     is not zero.

Let f(n) be the reciprocal Recaman and d(n) = A231593(n) be the reduced
denominator of f(n).
As noted earlier, the greatest prime factor gpf(d(n)) = A006530(d(n))
nondecreases.
In fact gpf(d(n)) = gpf(A002805(n)) = gpf(A003418(n)) = p(pi(n)) =
A000040(A000720(n)).
This means that distinct equal values d(n) = d(m) must lie in a narrow range
with p(i) <= n < m < p(i+1) for some prime p(i).

As you noted, there are places where f(n) < f(n-1) < f(n-2):

    s = (3 6 13 34 91 264 783 2342 7013 21030 63079 189236 567709 1703124
5109367 15328088 45984249 ...)

For a given I, the value of f(n) on the range n in [s(i), s(i+1))
alternately increase and decrease with strictly diminishing difference.
This means that there can be no duplicate values of f(n) on the range n in
[s(i), s(i+1)).
So if there exist n < m with f(n) = f(m), n and m must lie in different
ranges, i.e., n in [s(i), s(i+1)) and m in [s(j), s(j+1)) with I < j.

Further, we can show that s(i+1) >= 2 s(i).
Bertrand's postulate then gives us a prime number between s(i) and s(i+1),
so successive s(i) lie between different primes.
This is enough to conclude that gpf(d(s(i))) < gpf(d(s(i+1))).
>From which it follows that if n < m with f(n) = f(m), n and m must lie in
adjacent ranges, i.e., n in [s(i), s(i+1)) and m in [s(i+1), s(i+2)).

So if f(n) = f(m) with n < m, we must have

	p(j) < n < s(i) <= m < p(j+1)

for some i, where p(j) = gpf(d(s(i))).

In other words, if there are duplicate values of f(n), they lie very near
index s(i) for some i.
It remains to eliminate the possibility of duplicate f(n) for n in the
ranges [p(j), p(j+1)).

> --
> Don Reble  djr at nk.ca
> 
> 
> _______________________________________________
> 
> Seqfan Mailing list - http://list.seqfan.eu/