login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 274

%I #198 Jun 03 2023 23:57:44

%S 1,2,3,6,5,10,15,30,7,14,21,42,35,70,105,210,11,22,33,66,55,110,165,

%T 330,77,154,231,462,385,770,1155,2310,13,26,39,78,65,130,195,390,91,

%U 182,273,546,455,910,1365,2730,143,286,429,858,715,1430,2145,4290

%N 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 A permutation of the squarefree numbers A005117. The missing positive numbers are in A013929. - _Alois P. Heinz_, Sep 06 2014

%C From _Antti Karttunen_, Apr 18 & 19 2017: (Start)

%C Because a(n) toggles the parity of n there are neither fixed points nor any cycles of odd length.

%C 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 See also the slightly stronger conjecture in A285320, which implies that there would neither be any two-way infinite cycles.

%C 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 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 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 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 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 Reinhard Zumkeller, <a href="/A019565/b019565.txt">Table of n, a(n) for n = 0..8191</a>

%F G.f.: Product_{k>=0} (1 + prime(k+1)*x^2^k), where prime(k)=A000040(k). - _Ralf Stephan_, Jun 20 2003

%F 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 For all n >= 0: A048675(a(n)) = n; A013928(a(n)) = A064273(n). - _Antti Karttunen_, Jul 29 2015

%F 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 From _Antti Karttunen_, Apr 18 2017 and Jun 18 2017: (Start)

%F a(n) = A097248(A260443(n)), a(A005187(n)) = A283475(n), A108951(a(n)) = A283477(n).

%F A055396(a(n)) = A001511(n), a(A087207(n)) = A007947(n). (End)

%F a(2^n - 1) = A002110(n). - _Michael De Vlieger_, Jul 05 2017

%F a(n) = A225546(A000079(n)). - _Peter Munn_, Oct 31 2019

%F From _Peter Munn_, Mar 04 2022: (Start)

%F a(2n) = A003961(a(n)); a(2n+1) = 2*a(2n).

%F a(x XOR y) = A059897(a(x), a(y)) = A089913(a(x), a(y)), where XOR denotes bitwise exclusive OR (A003987).

%F a(n+1) = A334747(a(n)).

%F a(x+y) = A331590(a(x), a(y)).

%F a(n) = A336322(A008578(n+1)).

%F (End)

%e 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 From _Philippe Deléham_, Jun 03 2015: (Start)

%e This sequence regarded as a triangle withs rows of lengths 1, 1, 2, 4, 8, 16, ...:

%e 1;

%e 2;

%e 3, 6;

%e 5, 10, 15, 30;

%e 7, 14, 21, 42, 35, 70, 105, 210;

%e 11, 22, 33, 66, 55, 110, 165, 330, 77, 154, 231, 462, 385, 770, 1155, 2310;

%e ...

%e (End)

%e From _Peter Munn_, Jun 14 2020: (Start)

%e 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 n a(n)

%e 0 1 = .

%e 1 2 = 2.

%e 2 3 = 3.

%e 3 6 = 3*2.

%e 4 5 = 5.

%e 5 10 = 5*2.

%e 6 15 = 5*3.

%e 7 30 = 5*3*2.

%e 8 7 = 7.

%e 9 14 = 7*2.

%e 10 21 = 7*3.

%e 11 42 = 7*3*2.

%e 12 35 = 7*5.

%e (End)

%p a:= proc(n) local i, m, r; m:=n; r:=1;

%p for i while m>0 do if irem(m,2,'m')=1

%p then r:=r*ithprime(i) fi od; r

%p end:

%p seq(a(n), n=0..60); # _Alois P. Heinz_, Sep 06 2014

%t 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 Table[Times @@ Prime@ Flatten@ Position[#, 1] &@ Reverse@ IntegerDigits[n, 2], {n, 0, 55}] (* _Michael De Vlieger_, Aug 27 2016 *)

%t b[0] := {1}; b[n_] := Flatten[{ b[n - 1], b[n - 1] * Prime[n] }];

%t a = b[6] (* _Fred Daniel Kline_, Jun 26 2017 *)

%o (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 (Haskell)

%o a019565 n = product $ zipWith (^) a000040_list (a030308_row n)

%o -- _Reinhard Zumkeller_, Apr 27 2013

%o (Python)

%o from operator import mul

%o from functools import reduce

%o from sympy import prime

%o def A019565(n):

%o return reduce(mul,(prime(i+1) for i,v in enumerate(bin(n)[:1:-1]) if v == '1')) if n > 0 else 1

%o # _Chai Wah Wu_, Dec 25 2014

%o (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 Row 1 of A285321.

%Y Equivalent sequences for k-th-power-free numbers: A101278 (k=3), A101942 (k=4), A101943 (k=5), A054842 (k=10).

%Y Cf. A007088, A030308, A000040, A013929, A005117, A103785, A103786, A110765, A064273, A246353, A283475, A283477, A285319, A285331, A285332, A288569, A293442.

%Y Cf. A109162 (iterates).

%Y Cf. also A048675 (a left inverse), A087207, A097248, A260443, A054841.

%Y Cf. A285315 (numbers for which a(n) < n), A285316 (for which a(n) > n).

%Y Cf. A276076, A276086 (analogous sequences for factorial and primorial bases), A334110 (terms squared).

%Y For partial sums see A288570.

%Y A003961, A003987, A004198, A059897, A089913, A331590, A334747 are used to express relationships between sequence terms.

%Y Column 1 of A329332.

%Y Even bisection (which contains the odd terms): A332382.

%Y A160102 composed with A052330, and subsequence of the latter.

%Y Related to A000079 via A225546, to A057335 via A122111, to A008578 via A336322.

%Y Least prime index of a(n) is A001511.

%Y Greatest prime index of a(n) is A029837 or A070939.

%Y Taking prime indices gives A048793, reverse A272020, row sums A029931.

%Y A112798 lists prime indices, length A001222, sum A056239.

%Y Cf. A000120, A000720, A005940, A066099, A358137, A358170.

%K nonn,look,tabf

%O 0,2

%A _Marc LeBrun_

%E Definition corrected by Klaus-R. Löffler, Aug 20 2014

%E New name from _Peter Munn_, Jun 14 2020

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 16:58 EDT 2024. Contains 371254 sequences. (Running on oeis4.)