A285332 a(0) = 1, a(1) = 2, a(2n) = A019565(a(n)), a(2n+1) = A065642(a(n)).

1, 2, 3, 4, 6, 9, 5, 8, 15, 12, 14, 27, 10, 25, 7, 16, 210, 45, 35, 18, 105, 28, 462, 81, 21, 20, 154, 125, 30, 49, 11, 32, 10659, 420, 910, 75, 78, 175, 33, 24, 3094, 315, 385, 56, 780045, 924, 374, 243, 110, 63, 55, 40, 4389, 308, 170170, 625, 1155, 60, 286, 343, 42, 121, 13, 64, 54230826, 31977, 28405, 630, 1330665, 1820, 714

Offset: 0

Author

Antti Karttunen, Apr 17 2017

Keywords

• nonn
• tabf

Comments

Note the indexing: the domain starts from 0, while the range excludes zero.

This sequence can be represented as a binary tree. Each left hand child is produced as A019565(n), and each right hand child as A065642(n), when the parent node contains n >= 2:

1

|

...................2...................

3 4

6......../ \........9 5......../ \........8

/ \ / \ / \ / \

/ \ / \ / \ / \

/ \ / \ / \ / \

15 12 14 27 10 25 7 16

210 45 35 18 105 28 462 81 21 20 154 125 30 49 11 32

etc.

Where will 38 appear in this tree? It is a reasonable assumption that by iterating A087207 starting from 38, as A087207(38) = 129, A087207(129) = 8194, A087207(8194) = 1501199875790187, ..., we will eventually hit a prime A000040(k), most likely with a largish index k. This prime occurs at the penultimate edge at right, as a(A000918(k)) = a((2^k)-2), and thus 38 occurs somewhere below it as a(m) = 38, m > k. All the numbers that share prime factors with 38, namely 76, 152, 304, 608, 722, ..., occur similarly late in this tree, as they form the rightward branch starting from 38. Alternatively, by iterating A285330 (each iteration moves one step towards the root) starting from 38, we might instead first hit some power of 3, or say, one of the terms of A033845 (the rightward branch starting from 6), in which case the first prime encountered would be a(2)=3 and 38 would appear on the left-hand side instead of the right-hand side subtree.

As long as it remains conjecture that A019565 has no cycles, it is certainly also an open question whether this is a permutation of the natural numbers: If A019565 has any cycles, then neither any of the terms in those cycles nor any A065642-trajectories starting from those terms (that is, numbers sharing same prime factors) may occur in this tree.

Sequence exhibits some outrageous swings, for example, a(703) = 224, but a(704) is 1427 decimal digits (4739 binary digits) long, thus it no longer fits into a b-file.

However, the scatter plot of A286543 gives some flavor of the behavior of this sequence even after that point. - Antti Karttunen, Dec 25 2017

Links

• Antti Karttunen, Table of n, a(n) for n = 0..703
• Michael De Vlieger, Diagram of the binary tree of a(n) showing 1 <= n <= 2^8.
• Antti Karttunen and David J. Seal, Discussion on SeqFan mailing list
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Inverse: A285331.

Cf. A007947, A019565, A033845, A048675, A065642, A087207, A109162, A285319, A285320, A285328, A285330, A285333, A286542, A286543.

Compare also to permutation A285112 and array A285321.

Programs

Mathematica

Block[{a = {1, 2}}, Do[AppendTo[a, If[EvenQ[i], Times @@ Prime@ Flatten@ Position[#, 1] &@ Reverse@ IntegerDigits[a[[i/2 + 1]], 2], If[# == 1, 1, Function[{n, c}, SelectFirst[Range[n + 1, n^2], Times @@ FactorInteger[#][[All, 1]] == c &]] @@ {#, Times @@ FactorInteger[#][[All, 1]]}] &[a[[(i - 1)/2 + 1]] ] ]], {i, 2, 70}]; a] (* Michael De Vlieger, Mar 12 2021 *)

PARI

A019565(n) = {my(j,v); factorback(Mat(vector(if(n, #n=vecextract(binary(n), "-1..1")), j, [prime(j), n[j]])~))}; \\ This function from M. F. Hasler
A007947(n) = factorback(factorint(n)[, 1]); \\ From Andrew Lelechenko, May 09 2014
A065642(n) = { my(r=A007947(n)); if(1==n,n,n = n+r; while(A007947(n) <> r, n = n+r); n); };
A285332(n) = { if(n<=1,n+1,if(!(n%2),A019565(A285332(n/2)),A065642(A285332((n-1)/2)))); };
for(n=0, 4095, write("b285332.txt", n, " ", A285332(n)));

Python

from operator import mul
from sympy import prime, primefactors
def a007947(n): return 1 if n<2 else reduce(mul, primefactors(n))
def a019565(n): return reduce(mul, (prime(i+1) for i, v in enumerate(bin(n)[:1:-1]) if v == '1')) if n > 0 else 1 # This function from Chai Wah Wu
def a065642(n):
    if n==1: return 1
    r=a007947(n)
    n = n + r
    while a007947(n)!=r:
        n+=r
    return n
def a(n):
    if n<2: return n + 1
    if n%2==0: return a019565(a(n//2))
    else: return a065642(a((n - 1)//2))
print([a(n) for n in range(51)]) # Indranil Ghosh, Apr 18 2017

Scheme

;; With memoization-macro definec.
(definec (A285332 n) (cond ((<= n 1) (+ n 1)) ((even? n) (A019565 (A285332 (/ n 2)))) (else (A065642 (A285332 (/ (- n 1) 2))))))

Formula

a(0) = 1, a(1) = 2, a(2n) = A019565(a(n)), a(2n+1) = A065642(a(n)).

For n >= 0, a(2^n) = A109162(2+n). [The left edge of the tree.]

For n >= 0, a(A000225(n)) = A000079(n). [Powers of 2 occur at the right edge of the tree.]

For n >= 2, a(A000918(n)) = A000040(n). [And the next vertices inwards contain primes.]

For n >= 2, a(A036563(1+n)) = A001248(n). [Whose right children are their squares.]

For n >= 0, a(A055010(n)) = A000244(n). [Powers of 3 are at the rightmost edge of the left subtree.]

For n >= 2, a(A129868(n-1)) = A062457(n).

A048675(a(n)) = A285333(n).

A046523(a(n)) = A286542(n).