A356867 - OEIS

%I #60 Sep 17 2023 12:29:37

%S 1,2,3,5,4,6,10,8,9,7,14,15,25,20,12,50,16,18,35,28,30,125,40,24,100,

%T 32,27,11,22,21,55,44,42,70,56,45,49,98,75,175,140,60,250,80,36,245,

%U 196,150,625,200,48,500,64,54,77,110,105,275,88,84,350,112,90,343

%N For n >= 1, write n = 3^m + k, where m >= 0 is the greatest power of 3 <= n, and k is in the range 0 <= k < 3^(m+1) - 3^m, then for n such that k=0, a(n)=n, and for n such that k > 0, a(n) is the smallest prime multiple p*a(k), p != 3, that is not already a term.

%C Any prime p may be used to generate a sequence D(p) of this kind. The present sequence is D(3), and D(2) is the Doudna sequence, A005940.

%C Conjectured to be a permutation of the positive integers in which the primes appear in order.

%C From _Antti Karttunen_, Sep 16 2023: (Start)

%C The conjecture is true: Sequence is a permutation of natural numbers. By definition it is injective, and the surjectivity is guaranteed by the fact that there are infinitely many such n > k encountered by the greedy algorithm that a(n) will be a multiple of a(k), and "the smallest prime multiple" condition guarantees that all multiples of a(k) will eventually appear. That the primes and A100484 appear in order follows from the formulas a(3^m + 1) = prime(m+2), and a(3^m + 2) = 2*prime(m+2).

%C If the base-3 representation of n-1 has the base-3 representation of k-1 as its suffix, then a(n) is a multiple of a(k). For example, A007089(16-1) = 120, and A007089(43-1) = 1120, thus the former is the suffix of the latter, and a(16) = 50 indeed divides a(43) = 250.

%C (End)

%H Michael De Vlieger, <a href="/A356867/b356867.txt">Table of n, a(n) for n = 1..19683</a> (19683 = 3^9)

%H Michael De Vlieger, <a href="/A356867/a356867.png">Fan style ternary tree</a> showing a(n) for n = 1..3^9, with a heat map color function for level m where 3^m is blue, smaller values are bluer, and larger are yellow-green. The smallest value in level m is shown in purple and largest is shown in red.

%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>

%F a(3^m + 1) = prime(m+2) for m >= 1.

%F Conjectures from _Jianing Song_, Nov 23 2022: (Start)

%F (1) a(3^m+2) = 2*prime(m+2) for m >= 2. - [The conjecture is true because a(2) = 2 and 3^m + 2 < 3^(1+m) + (3^m) + 1 for all m - _Antti Karttunen_, Sep 16 2023]

%F (2) For n > m >= 1, a(3^n+3^m+1) = prime(m+2)^2 for n = m+1; prime(n+2)*prime(m+2)^2 for n >= m+2.

%F (3) For n > m >= 1, a(3^n+3^m+2) = 4*prime(n+2) for n >= 3, m = 1; 2*prime(m+2)^2 for n = m+1, m >= 2; 2*prime(m+2)*prime(m+3) for n = m+2, m >= 2; 2*prime(n+2)*prime(m+2)^2 for n >= m+3, m >= 2. (End)

%F From _Antti Karttunen_, Sep 17 2023: (Start)

%F If A053735(n) = 1, then a(n) = n, otherwise a(n) = A365424(n) * a(A365459(n)).

%F For all n >= 1, A007949(a(n)) = A007949(n) and a(3*n) = 3*a(n).

%F For n >= 1, a(3^n - 1) = 2^(2n - 1), a(A048473(n)) = 2^(2*(n-1)).

%F These are conjectures so far:

%F For n >= 1, a(3^n - 2) = 10^(n-1).

%F For n >= 2, a(3^n - 3) = A002023(n-2) = 6*4^(n-2).

%F (End)

%e n=1=3^0+0 so a(1)=1. n=2=3^0+1 so k=1 and a(2)=2. Similarly a(3)=3 and a(9)=9.

%e n=10=3^2+1, therefore k=1 and a(1)=1 so a(10)=1*7=7 (since 2 and 5 have already occurred).

%t nn = 64; m = 1; i = 2; p = Prime[i]; c[_] = False; Do[Set[{m, k}, {1, n - p^Floor[Log[p, n]]}]; If[k == 0, Set[{a[n], c[n]}, {n, True}], While[Set[t, Prime[m] a[k]]; Or[m == i, c[t]], m++]; Set[{a[n], c[t]}, {t, True}]], {n, nn}]; Array[a, nn] (* _Michael De Vlieger_, Sep 01 2022 *)

%o (Python)

%o from sympy import nextprime

%o from sympy.ntheory import digits

%o from itertools import count, islice

%o def b(n): return n - 3**(len(digits(n,3)) - 2)

%o def agen():

%o     aset, alst = set(), [None]

%o     for n in count(1):

%o         k = b(n)

%o         if k == 0: an = n

%o         else:

%o             ak, p = alst[k], 2

%o             while p == 3 or p*ak in aset: p = nextprime(p)

%o             an = p*ak

%o         yield an; aset.add(an); alst.append(an)

%o print(list(islice(agen(), 64))) # _Michael S. Branicky_, Sep 02 2022

%o (PARI)

%o up_to = 19683;

%o A356867list(up_to) = { my(v=vector(up_to),met=Map(),h=0,ak); for(i=1,#v,if(1==vecsum(digits(i,3)), v[i] = i; h = i, ak = v[i-h]; forprime(p=2,,if(3!=p && !mapisdefined(met,p*ak), v[i] = p*ak; break))); mapput(met,v[i],i)); (v); };

%o v356867 = A356867list(up_to);

%o A356867(n) = v356867[n]; \\ _Antti Karttunen_, Sep 15 2023

%Y Cf. A007089, A007949, A011655, A048473, A100484, A053735, A364958 (fixed points), A365390 (inverse permutation), A365424, A365459, A365462 [= a(n)-n], A365463 [= gcd(a(n),n)], A365464, A365465, A365717 [= A348717(a(1+n))], A365719 [= A046523(a(1+n))], A365721 [= omega(a(1+n))], A365722 [= bigomega(a(1+n))].

%Y Cf. also A005940, A364611, A364628 for variants D(2), D(5) and D(7).

%K nonn,look

%O 1,2

%A _David James Sycamore_, Sep 01 2022

%E More terms from _Michael De Vlieger_, Sep 01 2022