Displaying 1-10 of 13 results found.
Integer log of n: sum of primes dividing n (with repetition). Also called sopfr(n).
(Formerly M0461 N0168)
+10
679
0, 2, 3, 4, 5, 5, 7, 6, 6, 7, 11, 7, 13, 9, 8, 8, 17, 8, 19, 9, 10, 13, 23, 9, 10, 15, 9, 11, 29, 10, 31, 10, 14, 19, 12, 10, 37, 21, 16, 11, 41, 12, 43, 15, 11, 25, 47, 11, 14, 12, 20, 17, 53, 11, 16, 13, 22, 31, 59, 12, 61, 33, 13, 12, 18, 16, 67, 21, 26, 14, 71, 12, 73, 39, 13, 23, 18, 18
COMMENTS
MacMahon calls this the potency of n.
Downgrades the operators in a prime decomposition. E.g., 40 factors as 2^3 * 5 and sopfr(40) = 2 * 3 + 5 = 11.
Consider all ways of writing n as a product of zero, one, or more factors; sequence gives smallest sum of terms. - Amarnath Murthy, Jul 07 2001 a(n) <= n for all n, and a(n) = n iff n is 4 or a prime.
Look at the graph of this sequence. At the lower edge of the logarithmic scatterplot there is a set of fuzzy but unmistakable diagonal fringes, sloping toward the southeast. Their spacing gradually increases, and their slopes gradually decrease; they are more distinct toward the lower edge of the range. Is any explanation known? - Allan C. Wechsler, Oct 11 2015 For n >= 2, the glb and lub are: 3 * log(n) / log(3) <= a(n) <= n, where the lub occurs when n = 3^k, k >= 1. (Jakimczuk 2012) - Daniel Forgues, Oct 12 2015 Differs from A337310 beginning with n at 64, 192, 256, 320, 448, 512, ..., . The number of terms which equal k is A000607(k). The first occurrence of k>1 is A056240(k). The last occurrence of k>1 is A000792(k). The Amarnath Murthy comment of Jul 07 2001 is a result of the fundamental theorem of arithmetic. (End)
REFERENCES
K. Atanassov, New integer functions, related to ψ and σ functions. IV., Bull. Number Theory Related Topics 12 (1988), pp. 31-35.
Amarnath Murthy, Generalization of Partition function and introducing Smarandache Factor Partition, Smarandache Notions Journal, Vol. 11, 1-2-3, Spring-2000.
Amarnath Murthy and Charles Ashbacher, Generalized Partitions and Some New Ideas on Number Theory and Smarandache Sequences, Hexis, Phoenix; USA 2005. See Section 1.4.
Joe Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 89.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
Steve Witham, Linear-log plot (The clear upper lines are n (the primes), n/2, n/3, n/4... but there is a dark band at sqrt(n).) Steve Witham, Log-log plot (Differently interesting at the lower edge. Higher up, you can see sqrt(n), sqrt(n)/2, maybe sqrt(n)/3.)
FORMULA
If n = Product p_j^k_j then a(n) = Sum p_j * k_j.
Dirichlet g.f. f(s)*zeta(s), where f(s) = Sum_{p prime} p/(p^s-1) = Sum_{k>0} primezeta(k*s-1) is the Dirichlet g.f. for A120007. Totally additive with a(p^e) = p*e. - Franklin T. Adams-Watters, Jun 02 2006 Sum_{n>=1} (-1)^a(n)/n^s = ((2^s + 1)/(2^s - 1))*zeta(2*s)/zeta(s), if Re(s)>1 and 0 if s=1 (Alladi and Erdős, 1977). - Amiram Eldar, Nov 02 2020
EXAMPLE
a(24) = 2+2+2+3 = 9.
a(30) = 10: 30 can be written as 30, 15*2, 10*3, 6*5, 5*3*2. The corresponding sums are 30, 17, 13, 11, 10. Among these 10 is the least.
MAPLE
A001414 := proc(n) add( op(1, i)*op(2, i), i=ifactors(n)[2]) ; end proc:
MATHEMATICA
a[n_] := Plus @@ Times @@@ FactorInteger@ n; a[1] = 0; Array[a, 78] (* Ray Chandler, Nov 12 2005 *)
PROG
(PARI) a(n)=local(f); if(n<1, 0, f=factor(n); sum(k=1, matsize(f)[1], f[k, 1]*f[k, 2]))
(Haskell)
a001414 1 = 0
a001414 n = sum $ a027746_row n
(Sage) [sum(factor(n)[j][0]*factor(n)[j][1] for j in range(0, len(factor(n)))) for n in range(1, 79)] # Giuseppe Coppoletta, Jan 19 2015 (Python)
from sympy import factorint
return sum(p*e for p, e in factorint(n).items()) # Chai Wah Wu, Jan 08 2016 (Magma) [n eq 1 select 0 else (&+[j[1]*j[2]: j in Factorization(n)]): n in [1..100]]; // G. C. Greubel, Jan 10 2019
CROSSREFS
For sum of squares of prime factors see A067666, for cubes see A224787. Other completely additive sequences with primes p mapped to a function of p include: A001222 (with a(p)=1), A056239 (with a(p)=primepi(p)), A059975 (with a(p)=p-1), A064097 (with a(p)=1+a(p-1)), A113177 (with a(p)=Fib(p)), A276085 (with a(p)=p#/p), A341885 (with a(p)=p*(p+1)/2), A373149 (with a(p)=prevprime(p)), A373158 (with a(p)=p#). For other completely additive sequences see the cross-references in A104244.
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
246
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
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
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:
If n = 2^a * 3^b * 5^c * 7^d * ... then a(n) = a + 10 * b + 100 * c + 1000 * d + ... .
+10
29
0, 1, 10, 2, 100, 11, 1000, 3, 20, 101, 10000, 12, 100000, 1001, 110, 4, 1000000, 21, 10000000, 102, 1010, 10001, 100000000, 13, 200, 100001, 30, 1002, 1000000000, 111, 10000000000, 5, 10010, 1000001, 1100, 22, 100000000000, 10000001, 100010
COMMENTS
Are there any other numbers besides n=12 for which n=a(n) ? - Ctibor O. Zizka, Oct 08 2008 The sequence is a morphism from (N*,*) into (N,+), cf. formula. Up to n=1023, the digit sum A007953(a(n)) equals Omega(n) = A001222(n). This holds whenever A051903(n)<10. Restricted to these n, the sequence is also injective. However, when n is a multiple of 2^10, 3^10, 5^10 etc, then a(n) is equal to some a(m) with m<n. - M. F. Hasler, Nov 16 2008 This has been called the "Exponential Prime Power Representation" of n by W. Nissen in a post to the sci.math newsgroup (where probably some more sophisticated convention for representing digits > 10 would be used). - M. F. Hasler, Jul 03 2016
FORMULA
a(n) = Sum_{i>0} e_i*10^(i-1) when n = Product_{i>0} prime(i)^e_i. - M. F. Hasler, Mar 14 2018
EXAMPLE
a(25) = 200 because 25 = 5^2 * 3^0 * 2^0.
a(1024) = 10 = a(3), because 1024 = 2^10; but this two-digit multiplicity overflows into the 10^1 position, which encodes for powers of three.
MAPLE
A:= n -> add(t[2]*10^(numtheory:-pi(t[1])-1), t= ifactors(n)[2]);
MATHEMATICA
a054841[n_Integer] := Catch[FromDigits[IntegerDigits[Apply[Plus,
Which[n == 0, Throw["undefined"],
n == 1, 0,
Max[Last /@ FactorInteger @ n] > 9, Throw["overflow"],
True, Power[10, PrimePi[Abs[#]] - 1]] & /@
PROG
(PARI) A054841(n)=sum(i=1, #n=factor(n)~, 10^primepi(n[1, i])*n[2, i])/10 \\ M. F. Hasler, Nov 16 2008 (Haskell)
a054841 1 = 0
a054841 n = sum $ zipWith (*)
(map ((10 ^) . subtract 1 . a049084) $ a027748_row n)
(map fromIntegral $ a124010_row n)
(Python)
from sympy import factorint, primepi
def a(n): return sum(e*10**(primepi(p)-1) for p, e in factorint(n).items())
CROSSREFS
Cf. A001222, A048675, A090880, A090881, A090882, A276075, A276085 (analogous constructions for other bases), A090883, A090884, A049084, A027748, A124010, A056239.
Encoded multiplication table for polynomials in one indeterminate with nonnegative integer coefficients. Symmetric square array T(n, k) read by antidiagonals, n > 0 and k > 0. See comment for details.
+10
24
1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 5, 4, 1, 1, 5, 9, 9, 5, 1, 1, 6, 7, 16, 7, 6, 1, 1, 7, 15, 25, 25, 15, 7, 1, 1, 8, 11, 36, 11, 36, 11, 8, 1, 1, 9, 27, 49, 35, 35, 49, 27, 9, 1, 1, 10, 25, 64, 13, 90, 13, 64, 25, 10, 1, 1, 11, 21, 81, 125, 77, 77, 125, 81
COMMENTS
For any number n > 0, let f(n) be the polynomial in a single indeterminate x where the coefficient of x^e is the prime(1+e)-adic valuation of n (where prime(k) denotes the k-th prime); f establishes a bijection between the positive numbers and the polynomials in a single indeterminate x with nonnegative integer coefficients; let g be the inverse of f; T(n, k) = g(f(n) * f(k)).
This table has many similarities with A248601. For any n > 0 and m > 0, f(n * m) = f(n) + f(m).
Also, f(1) = 0 and f(2) = 1.
The function f can be naturally extended to the set of positive rational numbers: if r = u/v (not necessarily in reduced form), then f(r) = f(u) - f(v); as such, f is a homomorphism from the multiplicative group of positive rational numbers to the additive group of polynomials of a single indeterminate x with integer coefficients.
See A297473 for the main diagonal of T. As a binary operation, T(.,.) is related to A306697(.,.) and A329329(.,.). When their operands are terms of A050376 (sometimes called Fermi-Dirac primes) the three operations give the same result. However the rest of the multiplication table for T(.,.) can be derived from these results because T(.,.) distributes over integer multiplication ( A003991), whereas for A306697 and A329329, the equivalent derivation uses distribution over A059896(.,.) and A059897(.,.) respectively. - Peter Munn, Mar 25 2020 The operation defined by this sequence can be extended to be the multiplicative operator of a ring over the positive rationals that is isomorphic to the polynomial ring Z[x]. The extended function f (described in the author's original comments) is the isomorphism we use, and it has the same relationship with the extended operation that exists between their unextended equivalents.
Denoting this extension of T(.,.) as t_Q(.,.), we get t_Q(n, 1/k) = t_Q(1/n, k) = 1/T(n, k) and t_Q(1/n, 1/k) = T(n, k) for positive integers n and k. The result for other rationals is derived from the distributive property: t_Q(q, r*s) = t_Q(q, r) * t_Q(q, s); t_Q(q*r, s) = t_Q(q, s) * t_Q(r, s). This may look unusual because standard multiplication of rational numbers takes on the role of the ring's additive group.
There are many OEIS sequences that can be shown to be a list of the integers in an ideal of this ring. See the cross-references.
There are some completely additive sequences that similarly define by extension completely additive functions on the positive rationals that can be shown to be homomorphisms from this ring onto the integer ring Z, and these functions relate to some of the ideals. For example, the extended function of A048675, denoted A048675_Q, maps i/j to A048675(i) - A048675(j) for positive integers i and j. For any positive integer k, the set {r rational > 0 : k divides A048675_Q(r)} forms an ideal of the ring; for k=2 and k=3 the integers in this ideal are listed in A003159 and A332820 respectively. (End)
LINKS
Eric Weisstein's World of Mathematics, Ring.
FORMULA
T is completely multiplicative in both parameters:
- for any n > 0
- and k > 0 with prime factorization Prod_{i > 0} prime(i)^e_i:
- T(prime(n), k) = T(k, prime(n)) = Prod_{i > 0} prime(n + i - 1)^e_i.
For any m > 0, n > 0 and k > 0:
- T(n, k) = T(k, n) (T is commutative),
- T(m, T(n, k)) = T(T(m, n), k) (T is associative),
- T(n, 1) = 1 (1 is an absorbing element for T),
- T(n, 2) = n (2 is an identity element for T),
- T(n, 2^i) = n^i for any i >= 0,
- T(n, 3^i) = A003961(n)^i for any i >= 0, From Peter Munn, Mar 13 2020 and Apr 20 2021: (Start) T(n, m*k) = T(n, m) * T(n, k); T(n*m, k) = T(n, k) * T(m, k) (T distributes over multiplication).
(End)
EXAMPLE
Array T(n, k) begins:
n\k| 1 2 3 4 5 6 7 8 9 10
---+------------------------------------------------
3| 1 3 5 9 7 15 11 27 25 21 -> A003961 4| 1 4 9 16 25 36 49 64 81 100 -> A000290 5| 1 5 7 25 11 35 13 125 49 55 -> A357852 6| 1 6 15 36 35 90 77 216 225 210 -> A191002 7| 1 7 11 49 13 77 17 343 121 91
8| 1 8 27 64 125 216 343 512 729 1000 -> A000578 9| 1 9 25 81 49 225 121 729 625 441
10| 1 10 21 100 55 210 91 1000 441 550
The encoding, n, of polynomials, f(n), that is used for the table is further described in A206284. Examples of encoded polynomials: n f(n) n f(n)
1 0 16 4
2 1 17 x^6
3 x 21 x^3 + x
4 2 25 2x^2
5 x^2 27 3x
6 x + 1 35 x^3 + x^2
7 x^3 36 2x + 2
8 3 49 2x^3
9 2x 55 x^4 + x^2
10 x^2 + 1 64 6
11 x^4 77 x^4 + x^3
12 x + 2 81 4x
13 x^5 90 x^2 + 2x + 1
15 x^2 + x 91 x^5 + x^3
(End)
PROG
(PARI) T(n, k) = my (f=factor(n), p=apply(primepi, f[, 1]~), g=factor(k), q=apply(primepi, g[, 1]~)); prod (i=1, #p, prod(j=1, #q, prime(p[i]+q[j]-1)^(f[i, 2]*g[j, 2])))
CROSSREFS
Integers in the ideal of the related ring (see Jun 2021 comment) generated by S: S={3}: A005408, S={4}: A000290\{0}, S={4,3}: A003159, S={5}: A007310, S={5,4}: A339690, S={6}: A325698, S={6,4}: A028260, S={7}: A007775, S={8}: A000578\{0}, S={8,3}: A191257, S={8,6}: A332820, S={9}: A016754, S={10,4}: A340784, S={11}: A008364, S={12,8}: A145784, S={13}: A008365, S={15,4}: A345452, S={15,9}: A046337, S={16}: A000583\{0}, S={17}: A008366. Equivalent sequence for polynomial composition: A326376.
Prime factorization representation of Fibonacci polynomials: a(0) = 1, a(1) = 2, and for n > 1, a(n) = A003961(a(n-1)) * a(n-2).
+10
20
1, 2, 3, 10, 63, 2750, 842751, 85558343750, 2098355820117528699, 769999781728184386440152910156250, 2359414683424785920146467280333749864720543920418139851
COMMENTS
These are numbers matched to the Fibonacci polynomials according to the scheme explained in A206284 (see also A104244). In this case, the exponent of the k-th prime p_k in the prime factorization of a(n) indicates the coefficient of term x^(k-1) in the n-th Fibonacci polynomial. See the examples.
FORMULA
a(0) = 1, a(1) = 2, and for n >= 2, a(n) = A003961(a(n-1)) * a(n-2). Other identities. For all n >= 0:
A001222(a(n)) = A000045(n). [When each polynomial is evaluated at x=1.]
(End)
EXAMPLE
n a(n) prime factorization Fibonacci polynomial
------------------------------------------------------------
0 1 (empty) F_0(x) = 0
1 2 p_1 F_1(x) = 1
2 3 p_2 F_2(x) = x
3 10 p_3 * p_1 F_3(x) = x^2 + 1
4 63 p_4 * p_2^2 F_4(x) = x^3 + 2x
5 2750 p_5 * p_3^3 * p_1 F_5(x) = x^4 + 3x^2 + 1
6 842751 p_6 * p_4^4 * p_2^3 F_6(x) = x^5 + 4x^3 + 3x
MATHEMATICA
c[n_] := CoefficientList[Fibonacci[n, x], x]
f[n_] := Product[Prime[k]^c[n][[k]], {k, 1, Length[c[n]]}]
Table[f[n], {n, 1, 11}] (* A206296 *)
PROG
(Scheme, with memoization-macro definec)
(Python)
from sympy import factorint, prime, primepi
from operator import mul
def a003961(n):
F=factorint(n)
return 1 if n==1 else reduce(mul, [prime(primepi(i) + 1)**F[i] for i in F])
l=[1, 2]
for n in range(2, 11):
l.append(a003961(l[n - 1])*l[n - 2])
CROSSREFS
Other such mappings:
polynomial sequence integer sequence
-----------------------------------------
EXTENSIONS
a(0) = 1 prepended (to indicate 0-polynomial), Name changed, Comments and Example section rewritten by Antti Karttunen, Jul 29 2015
Suppose n=(p1^e1)(p2^e2)... where p1,p2,... are the prime numbers and e1,e2,... are nonnegative integers. Then a(n) = e1 + (e2)*3 + (e3)*9 + (e4)*27 + ... + (ek)*(3^(k-1)) + ...
+10
15
0, 1, 3, 2, 9, 4, 27, 3, 6, 10, 81, 5, 243, 28, 12, 4, 729, 7, 2187, 11, 30, 82, 6561, 6, 18, 244, 9, 29, 19683, 13, 59049, 5, 84, 730, 36, 8, 177147, 2188, 246, 12, 531441, 31, 1594323, 83, 15, 6562, 4782969, 7, 54, 19, 732, 245, 14348907, 10, 90, 30, 2190
COMMENTS
Replace "3" with "x" and extend the definition of a to positive rationals and a becomes an isomorphism between positive rationals under multiplication and polynomials over Z under addition. This remark generalizes A001222, A048675 and A054841: evaluate said polynomial at x=1, x=2 and x=10, respectively. For examples of such evaluations at x=3, see "Other identities" in the Formula section. - Antti Karttunen, Jul 31 2015
REFERENCES
Joseph J. Rotman, The Theory of Groups: An Introduction, 2nd ed. Boston: Allyn and Bacon, Inc. 1973. Page 9, problem 1.26.
FORMULA
Other identities. For all n >= 0:
CROSSREFS
Cf. A001222, A006190, A048675, A054841, A090881, A090882, A090883, A090884, A178590, A206296, A260443.
Write n as Product_{i=1..k} prime(i)^e_i, where prime(i) is the i-th prime number and e_i is a nonnegative integer. a(n) = Sum_{i=1..k} e_i*n^(i-1).
+10
8
0, 1, 3, 2, 25, 7, 343, 3, 18, 101, 14641, 14, 371293, 2745, 240, 4, 24137569, 37, 893871739, 402, 9282, 234257, 78310985281, 27, 1250, 11881377, 81, 21954, 14507145975869, 931, 819628286980801, 5, 1185954, 1544804417, 44100, 74
COMMENTS
In the definition, replace "e_i*n^(i-1)" with "e_i*x^(i-1)" for all i to define a function P:N+ -> N[x]. If we extend this definition to positive rationals by allowing negative e_i, P(.) becomes an isomorphism between positive rationals under multiplication and polynomials over Z under addition. We can use P to generalize A001222, A048675 and A054841: evaluate each term of the sequence of polynomials P(1), P(2), ... at x=1, x=2 and x=10, respectively. [Edited and corrected by Peter Munn, Aug 12 2022]
REFERENCES
Joseph J. Rotman, The Theory of Groups: An Introduction, 2nd ed. Boston: Allyn and Bacon, Inc. 1973. Page 9, problem 1.26.
PROG
(PARI) a(n) = my(f = factor(n)); sum(k=1, #f~, f[k, 2]*n^(primepi(f[k, 1])-1)); \\ Michel Marcus, Nov 01 2016
Triangle read by rows: Row n is the lexicographically earliest strictly monotonic completely additive sequence of length n.
+10
4
0, 0, 1, 0, 1, 2, 0, 2, 3, 4, 0, 2, 3, 4, 5, 0, 3, 5, 6, 7, 8, 0, 3, 5, 6, 7, 8, 9, 0, 4, 6, 8, 9, 10, 11, 12, 0, 5, 8, 10, 11, 13, 14, 15, 16, 0, 5, 8, 10, 12, 13, 14, 15, 16, 17, 0, 5, 8, 10, 12, 13, 14, 15, 16, 17, 18, 0, 7, 11, 14, 16, 18, 19, 21, 22, 23, 24, 25
COMMENTS
Each sequence consists of nonnegative integers indexed from 1.
Note in particular in the formula section, the lower bound, floor(n/k), for first differences between terms in a row. This follows (using the additive property) from the strict monotonicity of floor(n/k)+1 consecutive terms near the end of the row.
For any k, with increasing length n >= k, the first k terms of the sequences approach similarity with a real-valued logarithmic function defined on the integers. For example, the asymptote of T(n,3)/T(n,2) is log(3)/log(2), A020857.
FORMULA
The definition specifies: T(n,j*k) = T(n,j) + T(n,k); for k > 1, T(n,k) > T(n,k-1).
T(n,1) = 0, otherwise T(n,k) >= T(n,k-1) + floor(n/k).
For prime p, T(p,p) = T(p-1,p-1) + 1, otherwise T(p,k) = T(p-1,k).
T(n,2) >= 2*floor(n/4) + floor(n/9).
T(n,3) >= ceiling( (3*T(n,2) + floor(n/9)) / 2).
EXAMPLE
(For row 4.) A completely additive sequence requires T(4,1) = 0. Strict monotonicity requires T(4,4) > T(4,3) > T(4,2). So T(4,4) >= T(4,2) + 2. Using the additivity this becomes T(4,2) + T(4,2) >= T(4,2) + T(4,1) + 2. Subtracting T(4,2) and substituting 0 for T(4,1) we get T(4,2) >= 2. So from T(4,4) > T(4,3) > T(4,2), we see T(4,3) >= 3, T(4,4) >= 4. So row 4 = (0, 2, 3, 4) as it is strictly monotonic and completely additive and from the preceding arguments is seen to be the lexicographically earliest such.
Triangle starts:
0;
0, 1;
0, 1, 2;
0, 2, 3, 4;
0, 2, 3, 4, 5;
0, 3, 5, 6, 7, 8;
0, 3, 5, 6, 7, 8, 9;
0, 4, 6, 8, 9, 10, 11, 12;
0, 5, 8, 10, 11, 13, 14, 15, 16;
0, 5, 8, 10, 12, 13, 14, 15, 16, 17;
0, 5, 8, 10, 12, 13, 14, 15, 16, 17, 18;
0, 7, 11, 14, 16, 18, 19, 21, 22, 23, 24, 25;
0, 7, 11, 14, 16, 18, 19, 21, 22, 23, 24, 25, 26;
0, 7, 11, 14, 16, 18, 20, 21, 22, 23, 24, 25, 26, 27;
0, 8, 13, 16, 19, 21, 23, 24, 26, 27, 28, 29, 30, 31, 32;
0, 9, 14, 18, 21, 23, 25, 27, 28, 30, 31, 32, 33, 34, 35, 36;
CROSSREFS
Completely additive sequences, s, with primes p mapped to a function of s(p-1) and maybe s(p+1): A064097, A344443, A344444; and for functions of earlier terms, see A334200. For completely additive sequences with primes p mapped to a function of p, see A001414. For completely additive sequences with prime(k) mapped to a function of k, see A104244. For completely additive sequences where some primes are mapped to 1, the rest to 0 (notably, some ruler functions) see the cross-references in A249344.
Suppose n=(p1^e1)(p2^e2)... where p1,p2,... are the prime numbers and e1,e2,... are nonnegative integers. Then we can define Pn(x) = e1 + (e2)*x + (e3)*(x^2) + (e4)*(x^3) + ... + (ek)*(x^(k-1)) + ... The sequence is the table T(x,n)=Pn(x) read by antidiagonals.
+10
3
0, 0, 1, 0, 1, 1, 0, 1, 2, 2, 0, 1, 3, 2, 1, 0, 1, 4, 2, 4, 2, 0, 1, 5, 2, 9, 3, 1, 0, 1, 6, 2, 16, 4, 8, 3, 0, 1, 7, 2, 25, 5, 27, 3, 2, 0, 1, 8, 2, 36, 6, 64, 3, 4, 2, 0, 1, 9, 2, 49, 7, 125, 3, 6, 5, 1, 0, 1, 10, 2, 64, 8, 216, 3, 8, 10, 16, 3, 0, 1, 11, 2, 81, 9, 343, 3, 10, 17, 81, 4, 1, 0, 1, 12, 2
COMMENTS
This square array is the transpose of A104244, see comments there.
EXAMPLE
a(13)=3 because 3=(p1^0)(p2^1)(p3^0)..., so P3(x)=x. Hence a(13) = T(3,3) = P3(3) = 3.
The top left corner of the array:
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2
1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, 1331, 1728
3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3
2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24
2, 5, 10, 17, 26, 37, 50, 65, 82, 101, 122, 145
1, 16, 81, 256, 625, 1296, 2401, 4096, 6561, 10000, 14641, 20736
3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14
...
Numbers k such that there exists a positive integer B for which k = Sum_{i=0..m} (B^i)*a_i where the a_i are defined by k = Product_{i=0..m} prime(i+1)^a_i.
+10
3
3, 6, 10, 12, 24, 27, 36, 48, 96, 100, 144, 175, 192, 216, 273, 384, 486, 576, 768, 972, 1296, 1536, 1728, 2304, 3072, 3125, 6144, 9216, 12288, 13824, 17496, 19683, 20736, 24576, 36864, 46656, 49152, 62208, 69984, 98304, 110592, 147456, 196608, 331776, 393216, 589824
COMMENTS
Previous name: Numbers k such that there exists a solution to (p_m ^ a_m)*(p_m-1 ^ a_m-1)*...*(3^a_1)*(2^a_0) = (B^m)*a_m + (B^m-1)*a_m-1 + ... + (B^1)*a_1 + (B^0)*a_0 where k = (p_m ^ a_m)*(p_m-1 ^ a_m-1)*...*(3^a_1)*(2^a_0); a_m >= 1; a_(i<m) >= 0; p_0, p_1, ..., p_m are prime numbers; a_0, a_1, ..., a_m, B are integers.
B is the base in which we can express k as Sum_{i=0..m} B^i * a_i. B may also be seen as the variable in a polynomial, and k is then also an encoding of the polynomial (defined by the product of primes formula).
For k = (2^r)*3 we have B = (2^r)*3 - r.
A167221(n) is the smallest positive integer that yields a solution for k = a(n).
Negative B's can be obtained when the polynomial is an even function. This happens for instance when for k = 10, 100, 3125, ... - Michel Marcus, Aug 10 2022 Positive integers k such that k is a fixed point of a completely additive function f_B:N+ -> Z, B > 0, where f_B(prime(i+1)) = B^i for all i >= 0. Equivalently, since row B of A104244 is f_B, {a(n)} lists the columns of A104244 that contain their own column number. If we require B to be negative instead, the sequence appears to start 10, 100, 3125, 1799875, 65610000, ... . Of these, 1799875 = 5^3 * 7 * 11^2 * 17 is the only k with only negative solutions (B = -11); the solutions for 65610000 are {4049, -4051}.
(End)
If p is the (k+1)-th prime and p is congruent to 1 modulo k, then p^p is a term with p^((p-1)/k) a solution for B. The list of such primes starts 3, 5, 7, 31, 97, 101, 331, ... . I suspect this list is infinite, meaning the greatest prime factor of the terms would be unbounded. - Peter Munn, Aug 15 2022
EXAMPLE
For k = 10 = 2^1 * 3^0 * 5^1, k = B^0 * 1 + B^1 * 0 + B^2 * 1, so we have to solve the equation 10 = 1 + B^2 for a positive integer B, B = 3. But B=-3 works too. Thus 10 is a term.
For k = 12 = 2^2 * 3^1, k = B^0 * 2 + B^1 * 1, so we have to solve the equation 12 = 2 + B for a positive integer B. B = 10. Thus 12 is a term.
For k = 21 = 2^0 * 3^1 * 5^0 * 7^1, k = B^0 * 0 + B^1 * 1 + B^2 * 0 + B^3 * 1, so we have to solve the equation 21 = B + B^3 for an integer B. No such B exists, so 21 is not a term of this sequence.
In other words:
10 is a term because 10 = 5^1 * 3^0 * 2^1 and 101 in base 3 is 10.
12 is a term because 12 = 3^1 * 2^2 and 12 in base 10 is 12. (End)
PROG
(PARI) isok(k) = if (k>1, my(f=factor(k), v=primes(primepi(vecmax(f[, 1])))); my(p=sum(i=1, #v, 'x^(i-1)*valuation(k, v[i]))); p -= k; my(c=-polcoef(p, 0)); my(q=(p+c)/x); my(d=divisors(c)); for (k=1, #d, if(subst(q, x, d[k]) == c/d[k], return(1)); ); ); \\ Michel Marcus, Aug 08 2022 (Python)
from sympy import divisors, factorint, sieve
def ok(n):
if n < 2: return False
f = factorint(n)
a = [f[pi] if pi in f else 0 for pi in sieve.primerange(2, max(f)+1)]
for B in range(1, n+1):
polyB = sum(B**i*ai for i, ai in enumerate(a) if ai > 0)
if polyB == n: return True
elif polyB > n: return False
return False
CROSSREFS
A206284 describes the polynomial encoding used here.
EXTENSIONS
Incorrect term 71 removed, new name and more terms from Michel Marcus, Aug 08 2022
Search completed in 0.015 seconds
|