cp's OEIS Frontend

A019565 The squarefree numbers ordered lexicographically by their prime factorization (with factors written in decreasing order). a(n) = Product_{k in I} prime(k+1), where I is the set of indices of nonzero binary digits in n = Sum_{k in I} 2^k.

%I A019565 #198 Jun 03 2023 23:57:44
%S A019565 1,2,3,6,5,10,15,30,7,14,21,42,35,70,105,210,11,22,33,66,55,110,165,
%T A019565 330,77,154,231,462,385,770,1155,2310,13,26,39,78,65,130,195,390,91,
%U A019565 182,273,546,455,910,1365,2730,143,286,429,858,715,1430,2145,4290
%N A019565 The squarefree numbers ordered lexicographically by their prime factorization (with factors written in decreasing order). a(n) = Product_{k in I} prime(k+1), where I is the set of indices of nonzero binary digits in n = Sum_{k in I} 2^k.
%C A019565 A permutation of the squarefree numbers A005117. The missing positive numbers are in A013929. - _Alois P. Heinz_, Sep 06 2014
%C A019565 From _Antti Karttunen_, Apr 18 & 19 2017: (Start)
%C A019565 Because a(n) toggles the parity of n there are neither fixed points nor any cycles of odd length.
%C A019565 Conjecture: there are no finite cycles of any length. My grounds for this conjecture: any finite cycle in this sequence, if such cycles exist at all, must have at least one member that occurs somewhere in A285319, the terms that seem already to be quite rare. Moreover, any such a number n should satisfy in addition to A019565(n) < n also that A048675^{k}(n) is squarefree, not just for k=0, 1 but for all k >= 0. As there is on average a probability of only 6/(Pi^2) = 0.6079... that any further term encountered on the trajectory of A048675 is squarefree, the total chance that all of them would be squarefree (which is required from the elements of A019565-cycles) is soon minuscule, especially as A048675 is not very tightly bounded (many trajectories seem to skyrocket, at least initially). I am also assuming that usually there is no significant correlation between the binary expansions of n and A048675(n) (apart from their least significant bits), or, for that matter, between their prime factorizations.
%C A019565 See also the slightly stronger conjecture in A285320, which implies that there would neither be any two-way infinite cycles.
%C A019565 If either of the conjectures is false (there are cycles), then certainly neither sequence A285332 nor its inverse A285331 can be a permutation of natural numbers. (End)
%C A019565 The conjecture made in A087207 (see also A288569) implies the two conjectures mentioned above. A further constraint for cycles is that in any A019565-trajectory which starts from a squarefree number (A005117), every other term is of the form 4k+2, while every other term is of the form 6k+3. - _Antti Karttunen_, Jun 18 2017
%C A019565 The sequence satisfies the exponential function identity, a(x + y) = a(x) * a(y), whenever x and y do not have a 1-bit in the same position, i.e., when A004198(x,y) = 0. See also A283475. - _Antti Karttunen_, Oct 31 2019
%C A019565 The above identity becomes unconditional if binary exclusive OR, A003987(.,.), is substituted for addition, and A059897(.,.), a multiplicative equivalent of A003987, is substituted for multiplication. This gives us a(A003987(x,y)) = A059897(a(x), a(y)). - _Peter Munn_, Nov 18 2019
%C A019565 Also the Heinz number of the binary indices of n, where the Heinz number of a sequence (y_1,...,y_k) is prime(y_1)*...*prime(y_k), and a number's binary indices (A048793) are the positions of 1's in its reversed binary expansion. - _Gus Wiseman_, Dec 28 2022
%H A019565 Reinhard Zumkeller, <a href="/A019565/b019565.txt">Table of n, a(n) for n = 0..8191</a>
%F A019565 G.f.: Product_{k>=0} (1 + prime(k+1)*x^2^k), where prime(k)=A000040(k). - _Ralf Stephan_, Jun 20 2003
%F A019565 a(n) = f(n, 1, 1) with f(x, y, z) = if x > 0 then f(floor(x/2), y*prime(z)^(x mod 2), z+1) else y. - _Reinhard Zumkeller_, Mar 13 2010
%F A019565 For all n >= 0: A048675(a(n)) = n; A013928(a(n)) = A064273(n). - _Antti Karttunen_, Jul 29 2015
%F A019565 a(n) = a(2^x)*a(2^y)*a(2^z)*... = prime(x+1)*prime(y+1)*prime(z+1)*..., where n = 2^x + 2^y + 2^z + ... - _Benedict W. J. Irwin_, Jul 24 2016
%F A019565 From _Antti Karttunen_, Apr 18 2017 and Jun 18 2017: (Start)
%F A019565 a(n) = A097248(A260443(n)), a(A005187(n)) = A283475(n), A108951(a(n)) = A283477(n).
%F A019565 A055396(a(n)) = A001511(n), a(A087207(n)) = A007947(n). (End)
%F A019565 a(2^n - 1) = A002110(n). - _Michael De Vlieger_, Jul 05 2017
%F A019565 a(n) = A225546(A000079(n)). - _Peter Munn_, Oct 31 2019
%F A019565 From _Peter Munn_, Mar 04 2022: (Start)
%F A019565 a(2n) = A003961(a(n)); a(2n+1) = 2*a(2n).
%F A019565 a(x XOR y) = A059897(a(x), a(y)) = A089913(a(x), a(y)), where XOR denotes bitwise exclusive OR (A003987).
%F A019565 a(n+1) = A334747(a(n)).
%F A019565 a(x+y) = A331590(a(x), a(y)).
%F A019565 a(n) = A336322(A008578(n+1)).
%F A019565 (End)
%e A019565 5 = 2^2+2^0, e_1 = 2, e_2 = 0, prime(2+1) = prime(3) = 5, prime(0+1) = prime(1) = 2, so a(5) = 5*2 = 10.
%e A019565 From _Philippe Deléham_, Jun 03 2015: (Start)
%e A019565 This sequence regarded as a triangle withs rows of lengths 1, 1, 2, 4, 8, 16, ...:
%e A019565    1;
%e A019565    2;
%e A019565    3,  6;
%e A019565    5, 10, 15, 30;
%e A019565    7, 14, 21, 42, 35,  70, 105, 210;
%e A019565   11, 22, 33, 66, 55, 110, 165, 330, 77, 154, 231, 462, 385, 770, 1155, 2310;
%e A019565   ...
%e A019565 (End)
%e A019565 From _Peter Munn_, Jun 14 2020: (Start)
%e A019565 The initial terms are shown below, equated with the product of their prime factors to exhibit the lexicographic order. We start with 1, since 1 is factored as the empty product and the empty list is first in lexicographic order.
%e A019565    n     a(n)
%e A019565    0     1 = .
%e A019565    1     2 = 2.
%e A019565    2     3 = 3.
%e A019565    3     6 = 3*2.
%e A019565    4     5 = 5.
%e A019565    5    10 = 5*2.
%e A019565    6    15 = 5*3.
%e A019565    7    30 = 5*3*2.
%e A019565    8     7 = 7.
%e A019565    9    14 = 7*2.
%e A019565   10    21 = 7*3.
%e A019565   11    42 = 7*3*2.
%e A019565   12    35 = 7*5.
%e A019565 (End)
%p A019565 a:= proc(n) local i, m, r; m:=n; r:=1;
%p A019565       for i while m>0 do if irem(m,2,'m')=1
%p A019565         then r:=r*ithprime(i) fi od; r
%p A019565     end:
%p A019565 seq(a(n), n=0..60);  # _Alois P. Heinz_, Sep 06 2014
%t A019565 Do[m=1;o=1;k1=k;While[ k1>0, k2=Mod[k1, 2];If[k2\[Equal]1, m=m*Prime[o]];k1=(k1-k2)/ 2;o=o+1];Print[m], {k, 0, 55}] (* _Lei Zhou_, Feb 15 2005 *)
%t A019565 Table[Times @@ Prime@ Flatten@ Position[#, 1] &@ Reverse@ IntegerDigits[n, 2], {n, 0, 55}]  (* _Michael De Vlieger_, Aug 27 2016 *)
%t A019565 b[0] := {1}; b[n_] := Flatten[{ b[n - 1], b[n - 1] * Prime[n] }];
%t A019565   a = b[6] (* _Fred Daniel Kline_, Jun 26 2017 *)
%o A019565 (PARI) a(n)=factorback(vecextract(primes(logint(n+!n,2)+1),n))  \\ _M. F. Hasler_, Mar 26 2011, updated Aug 22 2014, updated Mar 01 2018
%o A019565 (Haskell)
%o A019565 a019565 n = product $ zipWith (^) a000040_list (a030308_row n)
%o A019565 -- _Reinhard Zumkeller_, Apr 27 2013
%o A019565 (Python)
%o A019565 from operator import mul
%o A019565 from functools import reduce
%o A019565 from sympy import prime
%o A019565 def A019565(n):
%o A019565     return reduce(mul,(prime(i+1) for i,v in enumerate(bin(n)[:1:-1]) if v == '1')) if n > 0 else 1
%o A019565 # _Chai Wah Wu_, Dec 25 2014
%o A019565 (Scheme) (define (A019565 n) (let loop ((n n) (i 1) (p 1)) (cond ((zero? n) p) ((odd? n) (loop (/ (- n 1) 2) (+ 1 i) (* p (A000040 i)))) (else (loop (/ n 2) (+ 1 i) p))))) ;; (Requires only the implementation of A000040 for prime numbers.) - _Antti Karttunen_, Apr 20 2017
%Y A019565 Row 1 of A285321.
%Y A019565 Equivalent sequences for k-th-power-free numbers: A101278 (k=3), A101942 (k=4), A101943 (k=5), A054842 (k=10).
%Y A019565 Cf. A007088, A030308, A000040, A013929, A005117, A103785, A103786, A110765, A064273, A246353, A283475, A283477, A285319, A285331, A285332, A288569, A293442.
%Y A019565 Cf. A109162 (iterates).
%Y A019565 Cf. also A048675 (a left inverse), A087207, A097248, A260443, A054841.
%Y A019565 Cf. A285315 (numbers for which a(n) < n), A285316 (for which a(n) > n).
%Y A019565 Cf. A276076, A276086 (analogous sequences for factorial and primorial bases), A334110 (terms squared).
%Y A019565 For partial sums see A288570.
%Y A019565 A003961, A003987, A004198, A059897, A089913, A331590, A334747 are used to express relationships between sequence terms.
%Y A019565 Column 1 of A329332.
%Y A019565 Even bisection (which contains the odd terms): A332382.
%Y A019565 A160102 composed with A052330, and subsequence of the latter.
%Y A019565 Related to A000079 via A225546, to A057335 via A122111, to A008578 via A336322.
%Y A019565 Least prime index of a(n) is A001511.
%Y A019565 Greatest prime index of a(n) is A029837 or A070939.
%Y A019565 Taking prime indices gives A048793, reverse A272020, row sums A029931.
%Y A019565 A112798 lists prime indices, length A001222, sum A056239.
%Y A019565 Cf. A000120, A000720, A005940, A066099, A358137, A358170.
%K A019565 nonn,look,tabf
%O A019565 0,2
%A A019565 _Marc LeBrun_
%E A019565 Definition corrected by Klaus-R. Löffler, Aug 20 2014
%E A019565 New name from _Peter Munn_, Jun 14 2020