A368900 LCM-transform of Doudna sequence.

1, 2, 3, 2, 5, 1, 3, 2, 7, 1, 1, 1, 5, 1, 3, 2, 11, 1, 1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 5, 1, 3, 2, 13, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 11, 1, 1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 5, 1, 3, 2, 17, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 13, 1, 1, 1, 1, 1, 1, 1, 1

Offset: 1

Author

David James Sycamore and Antti Karttunen, Jan 10 2024

Keywords

• nonn

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]
• Index entries for sequences related to binary expansion of n

Crossrefs

Cf. A000040, A000225, A000265, A005940, A005941, A007814, A023758, A368901.

List of LCM-transforms of permutations (permutation given in parentheses):

Cf. A265576 (A064413; note that the EKG sequence permutation does not satisfy the S-property).

In all following cases, the permutation satisfies the S-property:

Cf. A014963 (A000027),

Cf. A369028 (A253563), A369029 (A253565), A369030 (A163511), A369053 (A243353).

Cf. A369031 (A122111), A369032 (A241909), A369033 (A241916).

Cf. A369041 (A003188), A369042 (A006068), A369043 (A193231), A369044 (A057889), A369041 (A054429). [Base-2 related permutations]

Cf. A369060 (A356867).

Other permutations that have the same property: A303767, (and when used as an offset=1 sequence): A052330.

Programs

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 *)

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));
A368900(n)  = if(1==n, 1, my(x=A000265(n-1)); if(A209229(1+x), prime(1+valuation(n-1,2)), 1));

Formula

a(n) = A368901(n) / A368901(n-1) = lcm {1..A005940(n)} / lcm {1..A005940(n-1)}.

a(n) = A005940(n) / gcd(A005940(n), A368901(n-1)).

a(n) = A014963(A005940(n)). [Because A005940 satisfies the property given in the comments]

For n >= 1, Product_{d|n} a(A005941(d)) = n. [Implied by above]

For n >= 1, a(n) = A369030(1+A054429(n-1)).

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.