cp's OEIS Frontend

A368900 LCM-transform of Doudna sequence.

%I A368900 #72 Mar 24 2024 11:19:42
%S A368900 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,
%T A368900 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,
%U A368900 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
%N A368900 LCM-transform of Doudna sequence.
%C A368900 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.
%C A368900 Clearly the Doudna-sequence satisfies the property by the way of its construction, as do many of its variants like A356867 (see A369060).
%C A368900 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.
%C A368900 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.
%C A368900 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
%H A368900 Antti Karttunen, <a href="/A368900/b368900.txt">Table of n, a(n) for n = 1..65537</a>
%H A368900 A. Nowicki, <a href="http://arxiv.org/abs/1310.2416">Strong divisibility and LCM-sequences</a>, arXiv:1310.2416 [math.NT], 2013.
%H A368900 A. Nowicki, <a href="http://www.jstor.org/stable/10.4169/amer.math.monthly.122.10.958">Strong divisibility and LCM-sequences</a>, Am. Math. Mnthly 122 (2015), 958-966. [Defines the LCM-transform operation]
%H A368900 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%F A368900 a(n) = A368901(n) / A368901(n-1) = lcm {1..A005940(n)} / lcm {1..A005940(n-1)}.
%F A368900 a(n) = A005940(n) / gcd(A005940(n), A368901(n-1)).
%F A368900 a(n) = A014963(A005940(n)). [Because A005940 satisfies the property given in the comments]
%F A368900 For n >= 1, Product_{d|n} a(A005941(d)) = n. [Implied by above]
%F A368900 For n >= 1, a(n) = A369030(1+A054429(n-1)).
%F A368900 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.
%t A368900 nn = 120; Array[Set[{s[#], a[#]}, {#, #}] &, 2]; j = 2;
%t A368900 Do[If[EvenQ[n],
%t A368900   Set[s[n], 2 s[n/2]],
%t A368900   Set[s[n],
%t A368900     Times @@ Power @@@ Map[{Prime[PrimePi[#1] + 1], #2} & @@ # &,
%t A368900       FactorInteger[s[(n + 1)/2]]]]];
%t A368900   k = LCM[j, s[n]]; a[n] = k/j; j = k, {n, 3, nn}];
%t A368900 Array[a, nn] (* _Michael De Vlieger_, Mar 24 2024 *)
%o A368900 (PARI)
%o A368900 up_to = 16384;
%o A368900 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); };
%o A368900 A005940(n) = { my(p=2, t=1); n--; until(!n\=2, if((n%2), (t*=p), p=nextprime(p+1))); (t) };
%o A368900 v368900 = LCMtransform(vector(up_to,i,A005940(i)));
%o A368900 A368900(n) = v368900[n];
%o A368900 (PARI)
%o A368900 A000265(n) = (n>>valuation(n,2));
%o A368900 A209229(n) = (n && !bitand(n,n-1));
%o A368900 A368900(n)  = if(1==n, 1, my(x=A000265(n-1)); if(A209229(1+x), prime(1+valuation(n-1,2)), 1));
%Y A368900 Cf. A000040, A000225, A000265, A005940, A005941, A007814, A023758, A368901.
%Y A368900 List of LCM-transforms of permutations (permutation given in parentheses):
%Y A368900 Cf. A265576 (A064413; note that the EKG sequence permutation does not satisfy the S-property).
%Y A368900 In all following cases, the permutation satisfies the S-property:
%Y A368900 Cf. A014963 (A000027),
%Y A368900 Cf. A369028 (A253563), A369029 (A253565), A369030 (A163511), A369053 (A243353).
%Y A368900 Cf. A369031 (A122111), A369032 (A241909), A369033 (A241916).
%Y A368900 Cf. A369041 (A003188), A369042 (A006068), A369043 (A193231), A369044 (A057889), A369041 (A054429). [Base-2 related permutations]
%Y A368900 Cf. A369060 (A356867).
%Y A368900 Other permutations that have the same property: A303767, (and when used as an offset=1 sequence): A052330.
%K A368900 nonn
%O A368900 1,2
%A A368900 _David James Sycamore_ and _Antti Karttunen_, Jan 10 2024