

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.


228



1, 2, 3, 6, 5, 10, 15, 30, 7, 14, 21, 42, 35, 70, 105, 210, 11, 22, 33, 66, 55, 110, 165, 330, 77, 154, 231, 462, 385, 770, 1155, 2310, 13, 26, 39, 78, 65, 130, 195, 390, 91, 182, 273, 546, 455, 910, 1365, 2730, 143, 286, 429, 858, 715, 1430, 2145, 4290
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

A permutation of the squarefree numbers A005117. The missing positive numbers are in A013929.  Alois P. Heinz, Sep 06 2014
From Antti Karttunen, Apr 18 & 19 2017: (Start)
Because a(n) toggles the parity of n there are neither fixed points nor any cycles of odd length.
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 A019565cycles) 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.
See also the slightly stronger conjecture in A285320, which implies that there would neither be any twoway infinite cycles.
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)
The conjecture made in A087207 (see also A288569) implies the two conjectures mentioned above. A further constraint for cycles is that in any A019565trajectory 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
The sequence satisfies the exponential function identity, a(x + y) = a(x) * a(y), whenever x and y do not have a 1bit in the same position, i.e., when A004198(x,y) = 0. See also A283475.  Antti Karttunen, Oct 31 2019
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


LINKS

R. Zumkeller, Table of n, a(n) for n = 0..8191


FORMULA

G.f.: Product_{k>=0} (1 + prime(k+1)*x^2^k), where prime(k)=A000040(k).  Ralf Stephan, Jun 20 2003
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
For all n >= 0: A048675(a(n)) = n; A013928(a(n)) = A064273(n).  Antti Karttunen, Jul 29 2015
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
From Antti Karttunen, Apr 18 2017 and Jun 18 2017: (Start)
a(n) = A097248(A260443(n)), a(A005187(n)) = A283475(n), A108951(a(n)) = A283477(n).
A055396(a(n)) = A001511(n), a(A087207(n)) = A007947(n). (End)
a(2^n  1) = A002110(n).  Michael De Vlieger, Jul 05 2017
a(n) = A225546(A000079(n)).  Peter Munn, Oct 31 2019
a(A003987(x,y)) = A059897(a(x), a(y)).  Peter Munn, Nov 18 2019


EXAMPLE

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.
This sequence regarded as a triangle withs rows of lengths 1, 1, 2, 4, 8, 16, ...:
1;
2;
3, 6;
5, 10, 15, 30;
7, 14, 21, 42, 35, 70, 105, 210;
11, 22, 33, 66, 55, 110, 165, 330, 77, 154, 231, 462, 385, 770, 1155, 2310; ...
 Philippe Deléham, Jun 03 2015
From Peter Munn, Jun 14 2020: (Start)
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.
n a(n)
0 1 = .
1 2 = 2.
2 3 = 3.
3 6 = 3*2.
4 5 = 5.
5 10 = 5*2.
6 15 = 5*3.
7 30 = 5*3*2.
8 7 = 7.
9 14 = 7*2.
10 21 = 7*3.
11 42 = 7*3*2.
12 35 = 7*5.
(End)


MAPLE

a:= proc(n) local i, m, r; m:=n; r:=1;
for i while m>0 do if irem(m, 2, 'm')=1
then r:=r*ithprime(i) fi od; r
end:
seq(a(n), n=0..60); # Alois P. Heinz, Sep 06 2014


MATHEMATICA

Do[m=1; o=1; k1=k; While[ k1>0, k2=Mod[k1, 2]; If[k2\[Equal]1, m=m*Prime[o]]; k1=(k1k2)/ 2; o=o+1]; Print[m], {k, 0, 55}] (* Lei Zhou, Feb 15 2005 *)
Table[Times @@ Prime@ Flatten@ Position[#, 1] &@ Reverse@ IntegerDigits[n, 2], {n, 0, 55}] (* Michael De Vlieger, Aug 27 2016 *)
b[0] := {1}; b[n_] := Flatten[{ b[n  1], b[n  1] * Prime[n] }];
a = b[6] (* Fred Daniel Kline, Jun 26 2017 *)


PROG

(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
(Haskell)
a019565 n = product $ zipWith (^) a000040_list (a030308_row n)
 Reinhard Zumkeller, Apr 27 2013
(Python)
from operator import mul
from functools import reduce
from sympy import prime
def A019565(n):
return reduce(mul, (prime(i+1) for i, v in enumerate(bin(n)[:1:1]) if v == '1')) if n > 0 else 1
# Chai Wah Wu, Dec 25 2014
(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


CROSSREFS

Row 1 of A285321.
Cf. A101278, A054842, A007088, A030308, A000040, A013929, A005117, A103785, A103786, A110765, A064273, A225546, A246353, A283475, A283477, A285319, A285331, A285332, A288569, A293442.
Cf. A109162 (iterates).
Cf. also A048675 (a left inverse), A087207, A097248, A260443, A054841.
Cf. A285315 (numbers for which a(n) < n), A285316 (for which a(n) > n).
Cf. A276076, A276086 (analogous sequences for factorial and primorial bases).
For partial sums see A288570.
A003987, A004198 and A059897 are used to express relationships between sequence terms.
Sequence in context: A239956 A077320 A339195 * A309840 A340316 A274608
Adjacent sequences: A019562 A019563 A019564 * A019566 A019567 A019568


KEYWORD

nonn,look,tabf


AUTHOR

Marc LeBrun


EXTENSIONS

Definition corrected by KlausR. Löffler, Aug 20 2014
New name from Peter Munn, Jun 14 2020


STATUS

approved



