OFFSET
1,2
COMMENTS
Let's define "property S" for sequences as follows: If s is any sequence of positive natural numbers, normalized to begin with offset 1, then it satisfies the S-property if LCM-transform(s) is equal to the sequence obtained by applying A014963 to sequence s, or in other words, when for all n >= 1, lcm {s(1)..s(n)} / lcm {s(1)..s(n-1)} = A014963(s(n)). This holds if and only if, for all n >= 1, when, either (case A): s(n) is of the form p^k, p prime, then gcd(s(n), lcm {s(1)..s(n-1)}) must be equal to p^(k-1), or (case B): when s(n) is not a prime power, then gcd(s(n), lcm {s(1)..s(n-1)}) must be equal to s(n). Together the cases (A) and (B) reduce to the condition that each prime power should appear in s before any of its multiples do.
Clearly the Doudna-sequence satisfies the property by the way of its construction, as do many of its variants like A356867 (see A369060).
Also, for any base-2 related permutation b that keeps all the numbers of range [2^k, 2^(1+k)[ in the same range, i.e., if for all n >= 1, A000523(b(n)) = A000523(n), then the above property is automatically satisfied.
Furthermore, because in Doudna-sequence no multiple of any term is located on the same row as the term itself (see the tree-illustration in A005940), it follows that any composition of A005940 with any such base-2 related permutation as mentioned above also automatically satisfies the S-property, for example, the permutations A163511, A243353, A253563, A253565, A366260, A366263 and A366275.
Note: Like A005940 itself, also this sequence might be more logical with the starting offset 0 instead of 1, to better align with the underlying mapping from the binary expansion of n to the prime factorization. - Antti Karttunen, Jan 24 2024
LINKS
Antti Karttunen, Table of n, a(n) for n = 1..65537
A. Nowicki, Strong divisibility and LCM-sequences, arXiv:1310.2416 [math.NT], 2013.
A. Nowicki, Strong divisibility and LCM-sequences, Am. Math. Mnthly 122 (2015), 958-966. [Defines the LCM-transform operation]
FORMULA
For n >= 1, Product_{d|n} a(A005941(d)) = n. [Implied by above]
For n > 1, if n-1 is a number of the form 2^i - 2^j with i >= j, then a(n) = prime(1+j), otherwise a(n) = 1.
MATHEMATICA
nn = 120; Array[Set[{s[#], a[#]}, {#, #}] &, 2]; j = 2;
Do[If[EvenQ[n],
Set[s[n], 2 s[n/2]],
Set[s[n],
Times @@ Power @@@ Map[{Prime[PrimePi[#1] + 1], #2} & @@ # &,
FactorInteger[s[(n + 1)/2]]]]];
k = LCM[j, s[n]]; a[n] = k/j; j = k, {n, 3, nn}];
Array[a, nn] (* Michael De Vlieger, Mar 24 2024 *)
PROG
(PARI)
up_to = 16384;
LCMtransform(v) = { my(len = length(v), b = vector(len), g = vector(len)); b[1] = g[1] = 1; for(n=2, len, g[n] = lcm(g[n-1], v[n]); b[n] = g[n]/g[n-1]); (b); };
A005940(n) = { my(p=2, t=1); n--; until(!n\=2, if((n%2), (t*=p), p=nextprime(p+1))); (t) };
v368900 = LCMtransform(vector(up_to, i, A005940(i)));
A368900(n) = v368900[n];
(PARI)
A000265(n) = (n>>valuation(n, 2));
A209229(n) = (n && !bitand(n, n-1));
CROSSREFS
KEYWORD
nonn
AUTHOR
David James Sycamore and Antti Karttunen, Jan 10 2024
STATUS
approved