# [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
is not already in set S, then add it there.

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.
(and yes, this connection is already mentioned in its comments section
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)).

or try multiplication instead of addition, etc.

Have fun!

Antti
```