Search: a297845 -id:a297845
|
| |
|
|
A003961
|
|
Completely multiplicative with a(prime(k)) = prime(k+1).
|
|
+10
805
|
|
|
|
1, 3, 5, 9, 7, 15, 11, 27, 25, 21, 13, 45, 17, 33, 35, 81, 19, 75, 23, 63, 55, 39, 29, 135, 49, 51, 125, 99, 31, 105, 37, 243, 65, 57, 77, 225, 41, 69, 85, 189, 43, 165, 47, 117, 175, 87, 53, 405, 121, 147, 95, 153, 59, 375, 91, 297, 115, 93, 61, 315, 67, 111, 275, 729, 119
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
Meyers (see Guy reference) conjectures that for all r >= 1, the least odd number not in the set {a(i): i < prime(r)} is prime(r+1). - N. J. A. Sloane, Jan 08 2021
Meyers' conjecture would be refuted if and only if for some r there were such a large gap between prime(r) and prime(r+1) that there existed a composite c for which prime(r) < c < a(c) < prime(r+1), in which case (by Bertrand's postulate) c would necessarily be a term of A246281. - Antti Karttunen, Mar 29 2021
a(n) is odd for all n and for each odd m there exists a k with a(k) = m (see A064216). a(n) > n for n > 1: bijection between the odd and all numbers. - Reinhard Zumkeller, Sep 26 2001
Many permutations and other sequences that employ prime factorization of n to encode either polynomials, partitions (via Heinz numbers) or multisets in general can be easily defined by using this sequence as one of their constituent functions. See the last line in the Crossrefs section for examples.
(End)
|
|
|
REFERENCES
|
Richard K. Guy, editor, Problems From Western Number Theory Conferences, Labor Day, 1983, Problem 367 (Proposed by Leroy F. Meyers, The Ohio State U.).
|
|
|
LINKS
|
|
|
|
FORMULA
|
If n = Product p(k)^e(k) then a(n) = Product p(k+1)^e(k).
(End)
Sum_{k=1..n} a(k) ~ c * n^2, where c = (1/2) * Product_{p prime} ((p^2-p)/(p^2-nextprime(p))) = 2.06399637... . - Amiram Eldar, Nov 18 2022
|
|
|
EXAMPLE
|
a(12) = a(2^2 * 3) = a(prime(1)^2 * prime(2)) = prime(2)^2 * prime(3) = 3^2 * 5 = 45.
|
|
|
MAPLE
|
a:= n-> mul(nextprime(i[1])^i[2], i=ifactors(n)[2]):
|
|
|
MATHEMATICA
|
a[p_?PrimeQ] := a[p] = Prime[ PrimePi[p] + 1]; a[1] = 1; a[n_] := a[n] = Times @@ (a[#1]^#2& @@@ FactorInteger[n]); Table[a[n], {n, 1, 65}] (* Jean-François Alcover, Dec 01 2011, updated Sep 20 2019 *)
Table[Times @@ Map[#1^#2 & @@ # &, FactorInteger[n] /. {p_, e_} /; e > 0 :> {Prime[PrimePi@ p + 1], e}] - Boole[n == 1], {n, 65}] (* Michael De Vlieger, Mar 24 2017 *)
|
|
|
PROG
|
(PARI) a(n)=local(f); if(n<1, 0, f=factor(n); prod(k=1, matsize(f)[1], nextprime(1+f[k, 1])^f[k, 2]))
(PARI) a(n) = my(f = factor(n)); for (i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); \\ Michel Marcus, May 17 2014
(Haskell)
a003961 1 = 1
a003961 n = product $ map (a000040 . (+ 1) . a049084) $ a027746_row n
(MIT/GNU Scheme, with Aubrey Jaffer's SLIB Scheme library)
(require 'factor)
(Perl) use ntheory ":all"; sub a003961 { vecprod(map { next_prime($_) } factor(shift)); } # Dana Jacobsen, Mar 06 2016
(Python)
from sympy import factorint, prime, primepi, prod
def a(n):
f=factorint(n)
return 1 if n==1 else prod(prime(primepi(i) + 1)**f[i] for i in f)
|
|
|
CROSSREFS
|
Cf. A064989 (a left inverse), A064216, A000040, A002110, A000265, A027746, A046523, A048673 (= (a(n)+1)/2), A108228 (= (a(n)-1)/2), A191002 (= a(n)*n), A252748 (= a(n)-2n), A286385 (= a(n)-sigma(n)), A283980 (= a(n)*A006519(n)), A341529 (= a(n)*sigma(n)), A326042, A049084, A001221, A001222, A122111, A225546, A260443, A245606, A244319, A246269 (= A065338(a(n))), A322361 (= gcd(n, a(n))), A305293.
Cf. also following permutations and other sequences that can be defined with the help of this sequence: A005940, A163511, A122111, A260443, A206296, A265408, A265750, A275733, A275735, A297845, A091202 & A091203, A250245 & A250246, A302023 & A302024, A302025 & A302026.
Applying the same transformation again gives A045966.
|
|
|
KEYWORD
|
nonn,mult,nice
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A048675
|
|
If n = p_i^e_i * ... * p_k^e_k, p_i < ... < p_k primes (with p_i = prime(i)), then a(n) = (1/2) * (e_i * 2^i + ... + e_k * 2^k).
|
|
+10
241
|
|
|
|
0, 1, 2, 2, 4, 3, 8, 3, 4, 5, 16, 4, 32, 9, 6, 4, 64, 5, 128, 6, 10, 17, 256, 5, 8, 33, 6, 10, 512, 7, 1024, 5, 18, 65, 12, 6, 2048, 129, 34, 7, 4096, 11, 8192, 18, 8, 257, 16384, 6, 16, 9, 66, 34, 32768, 7, 20, 11, 130, 513, 65536, 8, 131072, 1025, 12, 6, 36, 19
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
COMMENTS
|
The original motivation for this sequence was to encode the prime factorization of n in the binary representation of a(n), each such representation being unique as long as this map is restricted to A005117 (squarefree numbers, resulting a permutation of nonnegative integers A048672) or any of its subsequence, resulting an injective function like A048623 and A048639.
However, also the restriction to A260443 (not all terms of which are squarefree) results a permutation of nonnegative integers, namely A001477, the identity permutation.
When a polynomial with nonnegative integer coefficients is encoded with the prime factorization of n (e.g., as in A206296, A260443), then a(n) gives the evaluation of that polynomial at x=2.
The primitive completely additive integer sequence that satisfies a(n) = a(A225546(n)), n >= 1. By primitive, we mean that if b is another such sequence, then there is an integer k such that b(n) = k * a(n) for all n >= 1. - Peter Munn, Feb 03 2020
If the binary rank of an integer partition y is given by Sum_i 2^(y_i-1), and the Heinz number is Product_i prime(y_i), then a(n) is the binary rank of the integer partition with Heinz number n. Note the function taking a set s to Sum_i 2^(s_i-1) is the inverse of A048793 (binary indices), and the function taking a multiset m to Product_i prime(m_i) is the inverse of A112798 (prime indices). - Gus Wiseman, May 22 2024
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(1) = 0, a(n) = 1/2 * (e1*2^i1 + e2*2^i2 + ... + ez*2^iz) if n = p_{i1}^e1*p_{i2}^e2*...*p_{iz}^ez, where p_i is the i-th prime. (e.g. p_1 = 2, p_2 = 3).
Totally additive with a(p^e) = e * 2^(PrimePi(p)-1), where PrimePi(n) = A000720(n). [Missing factor e added to the comment by Antti Karttunen, Jul 29 2015]
a(1) = 0; for n > 1, a(n) = 2^(A055396(n)-1) + a(A032742(n)). [Where A055396(n) gives the index of the smallest prime dividing n and A032742(n) gives the largest proper divisor of n.]
Other identities. For all n >= 0:
(End)
For n >= 2:
For n >= 1, the following chains hold:
(End)
|
|
|
EXAMPLE
|
The A018819(7) = 6 cases of binary rank 7 are the following, together with their prime indices:
30: {1,2,3}
40: {1,1,1,3}
54: {1,2,2,2}
72: {1,1,1,2,2}
96: {1,1,1,1,1,2}
128: {1,1,1,1,1,1,1}
(End)
|
|
|
MAPLE
|
nthprime := proc(n) local i; if(isprime(n)) then for i from 1 to 1000000 do if(ithprime(i) = n) then RETURN(i); fi; od; else RETURN(0); fi; end; # nthprime(2) = 1, nthprime(3) = 2, nthprime(5) = 3, etc. - this is also A049084.
A048675 := proc(n) local s, d; s := 0; for d in ifactors(n)[ 2 ] do s := s + d[ 2 ]*(2^(nthprime(d[ 1 ])-1)); od; RETURN(s); end;
# simpler alternative
f:= n -> add(2^(numtheory:-pi(t[1])-1)*t[2], t=ifactors(n)[2]):
|
|
|
MATHEMATICA
|
a[1] = 0; a[n_] := Total[ #[[2]]*2^(PrimePi[#[[1]]]-1)& /@ FactorInteger[n] ]; Array[a, 100] (* Jean-François Alcover, Mar 15 2016 *)
|
|
|
PROG
|
(Scheme, with memoization-macro definec, two alternatives)
(PARI) a(n) = my(f = factor(n)); sum(k=1, #f~, f[k, 2]*2^primepi(f[k, 1]))/2; \\ Michel Marcus, Oct 10 2016
(PARI)
\\ The following program reconstructs terms (e.g. for checking purposes) from the factorization file prepared by Hans Havermann:
v048675sigs = readvec("a048675.txt");
A048675(n) = if(n<=2, n-1, my(prsig=v048675sigs[n], ps=prsig[1], es=prsig[2]); prod(i=1, #ps, ps[i]^es[i])); \\ Antti Karttunen, Feb 02 2020
(Python)
from sympy import factorint, primepi
def a(n):
if n==1: return 0
f=factorint(n)
return sum([f[i]*2**(primepi(i) - 1) for i in f])
|
|
|
CROSSREFS
|
Pairs of sequences (f,g) that satisfy a(f(n)) = g(n), possibly with offset change: (A000203,A331750), (A005940,A087808), (A007913,A248663), (A007947,A087207), (A097248,A048675), (A206296,A000129), (A248692,A056239), (A283477,A005187), (A284003,A006068), (A285101,A028362), (A285102,A068052), (A293214,A001065), (A318834,A051953), (A319991,A293897), (A319992,A293898), (A320017,A318674), (A329352,A069359), (A332461,A156552), (A332462,A156552), (A332825,A000010) and apparently (A163511,A135529).
The formula section details how the sequence maps the terms of A329050, A329332.
The term k appears A018819(k) times.
The inverse transformation is A019565 (Heinz number of binary indices).
The version for distinct prime indices is A087207.
A014499 lists binary indices of prime numbers.
Binary indices:
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A066208
|
|
All primes that divide n are of the form prime(2k-1), where prime(k) is k-th prime.
|
|
+10
105
|
|
|
|
1, 2, 4, 5, 8, 10, 11, 16, 17, 20, 22, 23, 25, 31, 32, 34, 40, 41, 44, 46, 47, 50, 55, 59, 62, 64, 67, 68, 73, 80, 82, 83, 85, 88, 92, 94, 97, 100, 103, 109, 110, 115, 118, 121, 124, 125, 127, 128, 134, 136, 137, 146, 149, 155, 157, 160, 164, 166, 167, 170, 176, 179, 184
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
The partitions into odd parts, encoded by their Heinz numbers. We define the Heinz number of a partition p = [p_1, p_2, ..., p_r] as Product(p_j-th prime, j=1...r) (concept used by Alois P. Heinz in A215366 as an "encoding" of a partition). For example, for the partition [1, 1, 2, 4, 10] we get 2*2*3*7*29 = 2436. Example: 50 ( = 2*5*5) is in the sequence because it is the Heinz number of the partition [1, 3, 3]. - Emeric Deutsch, May 19 2015
Closed under multiplication.
Encodings, as defined in A206284, of even polynomials with nonnegative integer coefficients; so closed under application of A297845(.,.), which represents the multiplication of polynomials encoded this way.
(End)
For every positive integer m there exists a unique ordered pair of positive integers (j,k) such that m = a(j)*A066207(k). - Christopher Scussel, Aug 08 2023
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
20 is included because 20 = 2^2 * 5 = p(1)^2 * p(3) and 1 and 3 are both odd.
|
|
|
PROG
|
(PARI) { n=0; for (m=2, 10^9, f=factor(m); b=1; for(i=1, matsize(f)[1], if (primepi(f[i, 1])%2 == 0, b=0; break)); if (b, write("b066208.txt", n++, " ", m); if (n==1000, return)) ) } \\ Harry J. Smith, Feb 06 2010
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
| |
|
|
|
1, 2, 2, 4, 2, 6, 2, 8, 4, 10, 2, 12, 2, 14, 6, 16, 2, 18, 2, 20, 10, 22, 2, 24, 4, 26, 8, 28, 2, 30, 2, 32, 14, 34, 6, 36, 2, 38, 22, 40, 2, 42, 2, 44, 12, 46, 2, 48, 4, 50, 26, 52, 2, 54, 10, 56, 34, 58, 2, 60, 2, 62, 20, 64, 14, 66, 2, 68, 38, 70, 2, 72, 2
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
All terms except a(1) = 1 are even.
To compute a(n) for n > 1:
- if n = Product_{j = 1..o} prime(p_j)^e_j (where prime(i) denotes the i-th prime number, p_1 < ... < p_o and e_1 > 0)
- then a(n) = Product_{j = 1..o} prime(p_j + 1 - p_1)^e_j.
This sequence has similarities with A304776: here we shift down prime indexes, there prime exponents.
Smallest number generated by uniformly decrementing the indices of the prime factors of n. Thus, for n > 1, the smallest m > 1 such that the first differences of the indices of the ordered prime factors (including repetitions) are the same for m and n. As a function, a(.) preserves properties such as prime signature. - Peter Munn, May 12 2022
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = 2 iff n belongs to A000040 (prime numbers).
a(n) = 4 iff n belongs to A001248 (squares of prime numbers).
a(n) = 6 iff n belongs to A006094 (products of two successive prime numbers).
a(n) = 8 iff n belongs to A030078 (cubes of prime numbers).
a(n) = 10 iff n belongs to A090076.
a(n) = 12 iff n belongs to A251720.
a(n) = 14 iff n belongs to A090090.
a(n) = 16 iff n belongs to A030514.
a(n) = 30 iff n belongs to A046301.
a(n) = 32 iff n belongs to A050997.
a(n) = 36 iff n belongs to A166329.
a(1) = 1; a(2n) = 2n; a(A003961(n)) = a(n). [complete definition]
(End)
|
|
|
MATHEMATICA
|
a[1] = 1; a[n_] := Module[{f = FactorInteger[n], d}, d = PrimePi[f[[1, 1]]] - 1; Times @@ ((Prime[PrimePi[#[[1]]] - d]^#[[2]]) & /@ f)]; Array[a, 100] (* Amiram Eldar, Oct 31 2021 *)
|
|
|
PROG
|
(PARI) a(n) = { my (f=factor(n)); if (#f~>0, my (pi1=primepi(f[1, 1])); for (k=1, #f~, f[k, 1] = prime(primepi(f[k, 1])-pi1+1))); factorback(f) }
|
|
|
CROSSREFS
|
Positions of particular values (see formula section): A000040, A001248, A006094, A030078, A030514, A046301, A050997, A090076, A090090, A166329, A251720.
Also see formula section for the relationship to: A000265, A003961, A004277, A005940, A020639, A046523, A055396, A071364, A122111, A156552, A243055, A243074, A297845, A322993.
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A325698
|
|
Numbers with as many even as odd prime indices, counted with multiplicity.
|
|
+10
64
|
|
|
|
1, 6, 14, 15, 26, 33, 35, 36, 38, 51, 58, 65, 69, 74, 77, 84, 86, 90, 93, 95, 106, 119, 122, 123, 141, 142, 143, 145, 156, 158, 161, 177, 178, 185, 196, 198, 201, 202, 209, 210, 214, 215, 216, 217, 219, 221, 225, 226, 228, 249, 262, 265, 278, 287, 291, 299
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
These are Heinz numbers of the integer partitions counted by A045931.
A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.
The integers in the multiplicative subgroup of positive rational numbers generated by the products of two consecutive primes (A006094). The sequence is closed under multiplication, prime shift (A003961), and - where the result is an integer - under division. Using these closures, all the terms can be derived from the presence of 6. For example, A003961(6) = 15, A003961(15) = 35, 6 * 35 = 210, 210/15 = 14. Closed also under A297845, since A297845 can be defined using squaring, prime shift and multiplication. - Peter Munn, Oct 05 2020
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
The sequence of terms together with their prime indices begins:
1: {}
6: {1,2}
14: {1,4}
15: {2,3}
26: {1,6}
33: {2,5}
35: {3,4}
36: {1,1,2,2}
38: {1,8}
51: {2,7}
58: {1,10}
65: {3,6}
69: {2,9}
74: {1,12}
77: {4,5}
84: {1,1,2,4}
86: {1,14}
90: {1,2,2,3}
93: {2,11}
95: {3,8}
|
|
|
MATHEMATICA
|
Select[Range[100], Total[Cases[If[#==1, {}, FactorInteger[#]], {p_, k_}:>k*(-1)^PrimePi[p]]]==0&]
|
|
|
PROG
|
(PARI) is(n) = {my(v = vector(2), f = factor(n)); for(i = 1, #f~, v[1 + primepi(f[i, 1])%2]+=f[i, 2]); v[1] == v[2]} \\ David A. Corneth, Oct 06 2020
(Python)
from sympy import factorint, primepi
def ok(n):
v = [0, 0]
for p, e in factorint(n).items(): v[primepi(p)%2] += e
return v[0] == v[1]
|
|
|
CROSSREFS
|
Cf. A000712, A001222, A001405, A006094, A026010, A045931, A063886, A097613, A112798, A130780, A171966, A239241, A241638, A325700.
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A046337
|
|
Odd numbers with an even number of prime factors (counted with multiplicity).
|
|
+10
35
|
|
|
|
1, 9, 15, 21, 25, 33, 35, 39, 49, 51, 55, 57, 65, 69, 77, 81, 85, 87, 91, 93, 95, 111, 115, 119, 121, 123, 129, 133, 135, 141, 143, 145, 155, 159, 161, 169, 177, 183, 185, 187, 189, 201, 203, 205, 209, 213, 215, 217, 219, 221, 225, 235, 237, 247, 249, 253, 259
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
LINKS
|
|
|
|
FORMULA
|
|
|
|
MATHEMATICA
|
Select[Range[1, 301, 2], EvenQ[PrimeOmega[#]]&] (* Harvey P. Dale, Jul 25 2011 *)
|
|
|
PROG
|
(PARI) lista(nn) = {forstep(n=1, nn, 2, if (bigomega(n) % 2 == 0, print1(n, ", "))); } \\ Michel Marcus, Jul 04 2015
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A248663
|
|
Binary encoding of the prime factors of the squarefree part of n.
|
|
+10
35
|
|
|
|
0, 1, 2, 0, 4, 3, 8, 1, 0, 5, 16, 2, 32, 9, 6, 0, 64, 1, 128, 4, 10, 17, 256, 3, 0, 33, 2, 8, 512, 7, 1024, 1, 18, 65, 12, 0, 2048, 129, 34, 5, 4096, 11, 8192, 16, 4, 257, 16384, 2, 0, 1, 66, 32, 32768, 3, 20, 9, 130, 513, 65536, 6, 131072, 1025, 8, 0, 36, 19
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
COMMENTS
|
The binary digits of a(n) encode the prime factorization of A007913(n), where the i-th digit from the right is 1 if and only if prime(i) divides A007913(n), otherwise 0. - Robert Israel, Jan 12 2015
Old name: a(1) = 0; a(A000040(n)) = 2^(n-1), and a(n*m) = a(n) XOR a(m).
XOR is the bitwise exclusive or operation (A003987).
a(k^2) = 0 for a natural number k.
Equivalently, the i-th binary digit from the right is 1 iff prime(i) divides n an odd number of times, otherwise zero. - Ethan Beihl, Oct 15 2016
When a polynomial with nonnegative integer coefficients is encoded with the prime factorization of n (e.g., as in A206296, A260443, with scheme explained in A206284), then A048675(n) gives the evaluation of that polynomial at x=2. This sequence is otherwise similar, except the polynomial is evaluated over the field GF(2), which implies also that all its coefficients are essentially reduced modulo 2. - Antti Karttunen, Dec 11 2015
When we encode polynomials with nonnegative integer coefficients as described by Antti Karttunen above, polynomial addition is represented by integer multiplication, multiplication is represented by A297845(.,.), and this sequence represents a surjective semiring homomorphism to polynomials in GF(2)[x] (encoded as described in A048720). The mapping of addition operations by this homomorphism is part of the sequence definition: "a(n*m) = a(n) XOR a(m)". The mapping of multiplication is given by a(A297845(n, k)) = A048720(a(n), a(k)).
In a related way, A329329 defines a representation of a different set of polynomials as positive integers, namely polynomials in GF(2)[x,y].
Let P_n(x,y) denote the polynomial represented, as in A329329, by n >= 1. If 0 is substituted for y in P_n(x,y), we get a polynomial P'_n(x,y) (in which y does not appear, of course) that is equivalent to a polynomial P'_n(x) in GF(2)[x]. a(n) is the integer encoding of P'_n(x) (described in A048720).
Viewed as above, this sequence represents another surjective homomorphism, a homomorphism between polynomial rings, with A329329(.,.)/A059897(.,.) and A048720(.,.)/A003987(.,.) as the respective ring operations.
a(n) can be composed as a(n) = A048675(A007913(n)) and the effect of the A007913(.) component corresponds to different operations on the respective polynomial domains of the two homomorphisms described above. In the first homomorphism, coefficients are reduced modulo 2; in the second, 0 is substituted for y. This is illustrated in the examples.
(End)
|
|
|
LINKS
|
|
|
|
FORMULA
|
For n > 1, this simplifies to: a(n) = 2^(A055396(n)-1) XOR a(A032742(n)). [Where A055396(n) gives the index of the smallest prime dividing n and A032742(n) gives the largest proper divisor of n. Cf. a similar formula for A048675.]
Other identities and observations. For all n >= 0:
From Antti Karttunen, Dec 11 2015, Sep 19 & Oct 27 2016, Feb 15 2021: (Start)
a(n) = a(A007913(n)). [The result depends only on the squarefree part of n.]
(End)
From Peter Munn, Jan 09 2021 and Apr 20 2021: (Start)
(End)
|
|
|
EXAMPLE
|
a(3500) = a(2^2 * 5^3 * 7) = a(2) XOR a(2) XOR a(5) XOR a(5) XOR a(5) XOR a(7) = 1 XOR 1 XOR 4 XOR 4 XOR 4 XOR 8 = 0b0100 XOR 0b1000 = 0b1100 = 12.
The examples in the table below illustrate the homomorphisms (between polynomial structures) represented by this sequence.
The staggering of the rows is to show how the mapping n -> A007913(n) -> A048675(A007913(n)) = a(n) relates to the encoded polynomials, as not all encodings are relevant at each stage.
For an explanation of each polynomial encoding, see the sequence referenced in the relevant column heading. (Note also that A007913 generates squarefree numbers, and with these encodings, all squarefree numbers represent equivalent polynomials in N[x] and GF(2)[x,y].)
|<----- encoded polynomials ----->|
n A007913(n) a(n) | N[x] GF(2)[x,y] GF(2)[x]|
--------------------------------------------------------------
24 x+3 x+y+1
6 x+1 x+1
3 x+1
--------------------------------------------------------------
36 2x+2 xy+y
1 0 0
0 0
--------------------------------------------------------------
60 x^2+x+2 x^2+x+y
15 x^2+x x^2+x
6 x^2+x
--------------------------------------------------------------
90 x^2+2x+1 x^2+xy+1
10 x^2+1 x^2+1
5 x^2+1
--------------------------------------------------------------
This sequence is a left inverse of A019565. A019565(.) maps a(n) to A007913(n) for all n, effectively reversing the second stage of the mapping from n to a(n) shown above. So, with the encodings used here, A019565(.) represents each of two injective homomorphisms that map polynomials in GF(2)[x] to equivalent polynomials in N[x] and GF(2)[x,y] respectively.
(End)
|
|
|
MAPLE
|
f:= proc(n)
local F, f;
F:= select(t -> t[2]::odd, ifactors(n)[2]);
add(2^(numtheory:-pi(f[1])-1), f = F)
end proc:
|
|
|
MATHEMATICA
|
a[1] = 0; a[n_] := a[n] = If[PrimeQ@ n, 2^(PrimePi@ n - 1), BitXor[a[#], a[n/#]] &@ FactorInteger[n][[1, 1]]]; Array[a, 66] (* Michael De Vlieger, Sep 16 2016 *)
|
|
|
PROG
|
(Ruby)
require 'prime'
def f(n)
a = 0
reverse_primes = Prime.each(n).to_a.reverse
reverse_primes.each do |prime|
a <<= 1
while n % prime == 0
n /= prime
a ^= 1
end
end
a
end
(Scheme, with memoizing-macro definec)
;; Alternatively:
(PARI) A248663(n) = vecsum(apply(p -> 2^(primepi(p)-1), factor(core(n))[, 1])); \\ Antti Karttunen, Feb 15 2021
(Haskell)
import Data.Bits (xor)
a248663 = foldr (xor) 0 . map (\i -> 2^(i - 1)) . a112798_row
(Python)
from sympy import factorint, primepi
from sympy.ntheory.factor_ import core
def a048675(n):
f=factorint(n)
return 0 if n==1 else sum([f[i]*2**(primepi(i) - 1) for i in f])
def a(n): return a048675(core(n)) print [a(n) for n in range(1, 101)] # Indranil Ghosh, Jun 21 2017
|
|
|
CROSSREFS
|
A087207 is the analogous sequence with OR.
A000290 gives the positions of zeros.
|
|
|
KEYWORD
|
nonn,base
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A206284
|
|
Numbers that match irreducible polynomials over the nonnegative integers.
|
|
+10
28
|
|
|
|
3, 6, 9, 10, 12, 18, 20, 22, 24, 27, 28, 30, 36, 40, 42, 44, 46, 48, 50, 52, 54, 56, 60, 66, 68, 70, 72, 76, 80, 81, 88, 92, 96, 98, 100, 102, 104, 108, 112, 114, 116, 118, 120, 124, 126, 130, 132, 136, 140, 144, 148, 150, 152, 154, 160, 162, 164, 168, 170
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
Starting with 1, which encodes 0-polynomial, each integer m encodes (or "matches") a polynomial p(m,x) with nonnegative integer coefficients determined by the prime factorization of m. Write m = prime(1)^e(1) * prime(2)^e(2) * ... * prime(k)^e(k); then p(m,x) = e(1) + e(2)x + e(3)x^2 + ... + e(k)x^k.
Identities:
p(m*n,x) = p(m,x) + p(n,x),
p(m*n,x) = p(gcd(m,n),x) + p(lcm(m,n),x),
p(m+n,x) = p(gcd(m,n),x) + p((m+n)/gcd(m,n),x), so that if A003057 is read as a square matrix, then
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
Polynomials having nonnegative integer coefficients are matched to the positive integers as follows:
m p(m,x) irreducible
---------------------------
1 0 no
2 1 no
3 x yes
4 2 no
5 x^2 no
6 1+x yes
7 x^3 no
8 3 no
9 2x yes
10 1+x^2 yes
|
|
|
MAPLE
|
P:= n -> add(f[2]*x^(numtheory:-pi(f[1])-1), f = ifactors(n)[2]):
|
|
|
MATHEMATICA
|
b[n_] := Table[x^k, {k, 0, n}];
f[n_] := f[n] = FactorInteger[n]; z = 400;
t[n_, m_, k_] := If[PrimeQ[f[n][[m, 1]]] && f[n][[m, 1]]
== Prime[k], f[n][[m, 2]], 0];
u = Table[Apply[Plus,
Table[Table[t[n, m, k], {k, 1, PrimePi[n]}], {m, 1,
Length[f[n]]}]], {n, 1, z}];
p[n_, x_] := u[[n]].b[-1 + Length[u[[n]]]]
Table[p[n, x], {n, 1, z/4}]
v = {}; Do[n++; If[IrreduciblePolynomialQ[p[n, x]],
AppendTo[v, n]], {n, z/2}]; v (* A206284 *)
Complement[Range[200], v] (* A206285 *)
|
|
|
PROG
|
(PARI) is(n)=my(f=factor(n)); polisirreducible(sum(i=1, #f[, 1], f[i, 2]*'x^primepi(f[i, 1]-1))) \\ Charles R Greathouse IV, Feb 12 2012
|
|
|
CROSSREFS
|
Terms of A277318 form a proper subset of this sequence. Cf. also A277316.
Other sequences about factorization in the same polynomial ring: A206442, A284010.
Polynomial multiplication using the same encoding: A297845.
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A332823
|
|
A 3-way classification indicator generated by the products of two consecutive primes and the cubes of primes. a(n) is -1, 0, or 1 such that a(n) == A048675(n) (mod 3).
|
|
+10
25
|
|
|
|
0, 1, -1, -1, 1, 0, -1, 0, 1, -1, 1, 1, -1, 0, 0, 1, 1, -1, -1, 0, 1, -1, 1, -1, -1, 0, 0, 1, -1, 1, 1, -1, 0, -1, 0, 0, -1, 0, 1, 1, 1, -1, -1, 0, -1, -1, 1, 0, 1, 0, 0, 1, -1, 1, -1, -1, 1, 0, 1, -1, -1, -1, 0, 0, 0, 1, 1, 0, 0, 1, -1, 1, 1, 0, 1, 1, 0, -1, -1, -1, -1, -1, 1, 0, -1, 0, 1, 1, -1, 0
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
Completely additive modulo 3.
The equivalent sequence modulo 2 is A096268 (with offset 1), which produces the {A003159, A036554} classification.
Let H be the multiplicative subgroup of the positive rational numbers generated by the products of two consecutive primes and the cubes of primes. a(n) indicates the coset of H containing n. a(n) = 0 if n is in H. a(n) = 1 if n is in 2H. a(n) = -1 if n is in (1/2)H.
The properties of this classification can usefully be compared to two well-studied classifications. With the {A026424, A028260} classes, multiplying a member of one class by a prime gives a member of the other class. With the {A000028, A000379} classes, adding a factor to the Fermi-Dirac factorization of a member of one class gives a member of the other class. So, if 4 is not a Fermi-Dirac factor of k, k and 4k will be in different classes of the {A000028, A000379} set; but k and 4k will be in the same class of the {A026424, A028260} set. For two numbers to necessarily be in different classes when they differ in either of the 2 ways described above, 3 classes are needed.
With the classes defined by this sequence, no two of k, 2k and 4k are in the same class. This is a consequence of the following stronger property: if k is any positive integer and m is a member of A050376 (often called Fermi-Dirac primes), then no two of k, k * m, k * m^2 are in the same class. Also, if p and q are consecutive primes, then k * p and k * q are in different classes.
The scaled imaginary part of the Eisenstein integer-valued function, f, defined in A353445. - Peter Munn, Apr 27 2022
|
|
|
LINKS
|
|
|
|
FORMULA
|
For all n >= 1, k >= 1: (Start)
a(n * k) == a(n) + a(k) (mod 3).
a(A331590(n,k)) == a(n) + a(k) (mod 3).
a(n^2) = -a(n).
(End)
For all n >= 1: (Start)
(End)
|
|
|
PROG
|
(PARI) A332823(n) = { my(f = factor(n), u=(sum(k=1, #f~, f[k, 2]*2^primepi(f[k, 1]))/2)%3); if(2==u, -1, u); };
|
|
|
CROSSREFS
|
Cf. A353354 (inverse Möbius transform, gives another 3-way classification indicator function).
|
|
|
KEYWORD
|
sign
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A329332
|
|
Table of powers of squarefree numbers, powers of A019565(n) in increasing order in row n. Square array A(n,k) n >= 0, k >= 0 read by descending antidiagonals.
|
|
+10
24
|
|
|
|
1, 1, 1, 1, 2, 1, 1, 4, 3, 1, 1, 8, 9, 6, 1, 1, 16, 27, 36, 5, 1, 1, 32, 81, 216, 25, 10, 1, 1, 64, 243, 1296, 125, 100, 15, 1, 1, 128, 729, 7776, 625, 1000, 225, 30, 1, 1, 256, 2187, 46656, 3125, 10000, 3375, 900, 7, 1, 1, 512, 6561, 279936, 15625, 100000, 50625, 27000, 49, 14
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,5
|
|
|
COMMENTS
|
Transposition of this table, that is reflection about its main diagonal, has subtle symmetries. For example, consider the unique factorization of a number into powers of distinct primes. This can be restated as factorization into numbers from rows 2^n (n >= 0) with no more than one from each row. Reflecting about the main diagonal, this factorization becomes factorization (of a related number) into numbers from columns 2^k (k >= 0) with no more than one from each column. This is also unique and is factorization into powers of squarefree numbers with distinct exponents that are powers of two. See the example section.
|
|
|
LINKS
|
|
|
|
FORMULA
|
A(n,2k) = A000290(A(n,k)) = A(n,k)^2.
A(n,2k+1) = A(n,2k) * A(n,1).
A(2n+1,k) = A(2n,k) * A(1,k).
A(n,k) = A297845(A(n,1), A(1,k)) = A306697(A(n,1), A(1,k)), = A329329(A(n,1), A(1,k)).
Sum_{n>=0} 1/A(n,k) = zeta(k)/zeta(2*k), for k >= 2. - Amiram Eldar, Dec 03 2022
|
|
|
EXAMPLE
|
Square array A(n,k) begins:
n\k | 0 1 2 3 4 5 6 7
----+------------------------------------------------------------------
0| 1 1 1 1 1 1 1 1
1| 1 2 4 8 16 32 64 128
2| 1 3 9 27 81 243 729 2187
3| 1 6 36 216 1296 7776 46656 279936
4| 1 5 25 125 625 3125 15625 78125
5| 1 10 100 1000 10000 100000 1000000 10000000
6| 1 15 225 3375 50625 759375 11390625 170859375
7| 1 30 900 27000 810000 24300000 729000000 21870000000
8| 1 7 49 343 2401 16807 117649 823543
9| 1 14 196 2744 38416 537824 7529536 105413504
10| 1 21 441 9261 194481 4084101 85766121 1801088541
11| 1 42 1764 74088 3111696 130691232 5489031744 230539333248
12| 1 35 1225 42875 1500625 52521875 1838265625 64339296875
Reflection of factorization about the main diagonal: (Start)
The canonical (prime power) factorization of 864 is 2^5 * 3^3 = 32 * 27. Reflecting the factors about the main diagonal of the table gives us 10 * 36 = 10^1 * 6^2 = 360. This is the unique factorization of 360 into powers of squarefree numbers with distinct exponents that are powers of two.
Reflection about the main diagonal is given by the self-inverse function A225546(.). Clearly, all positive integers are in the domain of A225546, whether or not they appear in the table. It is valid to start from 360, observe that A225546(360) = 864, then use 864 to derive 360's factorization into appropriate powers of squarefree numbers as above.
(End)
|
|
|
CROSSREFS
|
Rows (abbreviated list): A000079(1), A000244(2), A000400(3), A000351(4), A011557(5), A001024(6), A009974(7), A000420(8), A001023(9), A009965(10), A001020(16), A001022(32), A001026(64).
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
Search completed in 0.025 seconds
|
