[seqfan] A327969, the shortest escape out of the labyrinth.

[Antti Karttunen]

This concerns https://oeis.org/A327969

We have a labyrinth of hexagonal rooms (my apologies to JLB!), each
room having its unique number 1, 2, 3, ..., etc from N+. From each room
there are exactly two exits, via corridors labeled "A003415" and
"A276086", leading to two (*) other, almost similar looking rooms. One
has found one's way out of the maze when one encounters a room with a
prime number, as then A003415(prime) = 1, the room #1 being a special one,
as from there is the only exit out of the maze as A003415(1) = 0.
There are turnstiles in the corridors, so in principle one cannot
backtrack (the edges of the graphs are unidirectional), except in
one's mind, perhaps.

(* except from the room #6 from where both corridors lead to the room #5).

Two questions:

1) Are there any rooms, from which one never can find one's way out of
the maze (i.e., n for which A327969(n) = -1 by its escape clause) ?

2) What is the true value of A327969(24) ? And of A327969(27) ? That
is, are there any paths from 24 to 0 shorter than 11 steps?
Or from 27 to 0 that are shorter than 22 steps?

About the choice of  A003415 and A276086 for the edges of the graph.
They are kind of reciprocal in a thematic sense (even though the real
inverse of A276086 is A276085): A003415 (arithmetic derivative)
decomposes number by its multiplicative structure, and reconstructs it
additively, while A270686 deconstructs number by its "additive
structure" (according to its primorial base expansion), and
reconstructs it multiplicatively.

Furthermore, sequences A100716 (Numbers n such that p^p divides n for
some prime p) and its complement A048103 are significant for both:
If iterating A003415 we ever come across of any term of A100716, then
there's no more hope of reaching a prime by iterating solely with
A003415, as then the numbers just keep on growing (or at best, stay
same for p^p), and will always have a factor of the form p^p. On the
other hand, the result of A276086 is never in A100716, as it is a
permutation of A048103.

Thus, if a lonely librarian in the labyrinth finds that when following
corridors labeled "A003415" the room numbers are always multiples of 4
(or 27, or 3125, etc) and keep on growing, then he can take instead
the corridor labeled "A276086", and then certainly the new room is
never a multiple of 4, 27, 3125, etc., and might still offer a way out
of the maze via a prime number. However, there is a catch with this:
usually the room number at the other size of A276086 is much larger
than that of from where one left off, and among the larger numbers, it
is more difficult to find primes.

One often workable heuristics is to always choose the corridor leading
to the room whose number is smaller of the two, i.e., iterate with
A328099(n) = min(A003415(n), A276086(n)). However, that doesn't always
lead to the most optimal solution (the shortest path to zero).

Also, even when the room number contains a factor of the form p^p, it
still might be better to keep on continuing following the
A003415-route, and not to take A276086-turn before one has arrived
with a number that is only "slightly more" than the nearest primorial
number (A002110) below, as then the maximal digit present in the
primorial base of that number wont be so high. This because A276086-map
converts that maximal digit to a maximal exponent in the prime
factorization of n,
which in turn affects the result of A003415. E.g., for A003415 to yield a prime,
its argument must be squarefree.


Note that the iterates of A276086 grow so fast that an exhaustive
computer search for an optimal solution is out of question already for
n=24. But there might be some other ways to deduce it. For example,
some of the combinations of A003415 and A276086 behave somewhat
nicely, see e.g. A328391, while others can be more chaotic.

Further idea: Could we let a deep learning neural network loose on
this (or similar) labyrinth, with zero default assumptions, and no
prior knowledge about A003415 and A276086, how they are computed, and
then see what could it make out of it? E.g., avoid for too long
following exits labeled "A003415" when in rooms that are multiples of
4, etc.
This rises the question how such neural net would represent a number,
whether say, in binary (where the two rightmost bits would then tell
whether a multiple of 4) or as a prime factorization vector. The
problem here is that the other "door", A276086, soon ("oracularly")
issues numbers that are too large and unwieldy for any representation.


Best regards,

Antti