# [seqfan] Finding sequences suitable for recursion formulas of type a(n) = 1 + a(Axxxxxx(n)).

Antti Karttunen antti.karttunen at gmail.com
Sun Sep 27 18:32:59 CEST 2015

```Here's a project for anybody who likes to play with OEIS data and to
find masses of unproved conjectures (as well as many "but of
course..." moments):

First filter out all sequences with either a(0) = 0 or, if starting
offset is one, with a(1) = 0 or a(1) = 1, and which seem to satisfy
a(k) < k for all the rest of terms. Call that set of sequences the set
S. (How large it is currently?)

E.g. A004526 Nonnegative integers repeated, floor(n/2).
starting from a(0) as: 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, ..., clearly fits the bill.

Then for each sequence s in S, construct another sequence defined just
as t(n) = n - s(n), for all n after the initial value (which depends
on the initial value and offset of the sequence s). If the sequence t

E.g. from

A032742 a(1) = 1; for n > 1, a(n) = largest proper divisor of n.
1, 1, 1, 2, 1, 3, 1, 4, 3, 5, 1, 6, 1, 7, 5, 8, 1, 9, 1, ....

we get t(n) = n - A032742(n)
which is A060681, "Largest difference between consecutive divisors of
n (ordered by size)."
but with also the term t(1) defined as t(1) = 0.
(As an aside: I suggest adding A060681(1) = 0 to that entry, as it
fits the current description, as 1 has no two consecutive divisors:
think about doing a "fold" over differences of consecutive divisors,
with max-function, starting from the initial-value zero.)

But back to the topic. Now, with each s from that extended set of S,
construct a simple "number of s-steps to reach the start" style
recurrence:

a(soff) = sval, a(n > soff) = 1 + a(s(n)).

and check whether it happens to be in OEIS, and does it refer to s in any way?

Here soff (starting offset) is either 0 or 1, and sval is similarly
either 0 or 1, depending from the initial conditions of s. If multiple
combinations of these values would work with the given s-sequence,
check for all of them.

E.g., with
a(1) = 0, for n > 1, a(n) = 1 + a(A032742(n)).
we get A001222 (the bigomega).

With
a(1) = 0, for n > 1, a(n) = 1 + a(A060681(n)).
we get:
A064097 A quasi-logarithm defined inductively by a(1) = 0 and a(p) = 1
+ a(p-1) if p is prime and a(n*m) = a(n) + a(m) if m,n > 1.
by Jaroslav Krizek).

And if this is not yet enough, you can try wilder functions than
A000012 at the left side of sum, e.g. define the non-initial part of
the recurrence as:

a(n) = n + a(s(n)).
or
a(n) = A000035(n) + a(s(n)).