login
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.
3

%I #74 Aug 16 2022 16:08:11

%S 3,6,10,12,24,27,36,48,96,100,144,175,192,216,273,384,486,576,768,972,

%T 1296,1536,1728,2304,3072,3125,6144,9216,12288,13824,17496,19683,

%U 20736,24576,36864,46656,49152,62208,69984,98304,110592,147456,196608,331776,393216,589824

%N 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.

%C 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.

%C 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).

%C For k = (2^r)*3 we have B = (2^r)*3 - r.

%C A167221(n) is the smallest positive integer that yields a solution for k = a(n).

%C 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

%C From _Peter Munn_, Aug 13 2022: (Start)

%C 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.

%C 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}.

%C (End)

%C 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

%H David A. Corneth, <a href="/A167219/b167219.txt">Table of n, a(n) for n = 1..98</a> (terms <= 10^10)

%H David A. Corneth, <a href="/A167219/a167219.gp.txt">PARI program</a>

%e 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.

%e 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.

%e 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.

%e From _Michel Marcus_, Aug 10 2022: (Start)

%e In other words:

%e 10 is a term because 10 = 5^1 * 3^0 * 2^1 and 101 in base 3 is 10.

%e 12 is a term because 12 = 3^1 * 2^2 and 12 in base 10 is 12. (End)

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

%o (PARI) \\ See PARI link \\ _David A. Corneth_, Aug 10 2022

%o (Python)

%o from sympy import divisors, factorint, sieve

%o def ok(n):

%o if n < 2: return False

%o f = factorint(n)

%o a = [f[pi] if pi in f else 0 for pi in sieve.primerange(2, max(f)+1)]

%o for B in range(1, n+1):

%o polyB = sum(B**i*ai for i, ai in enumerate(a) if ai > 0)

%o if polyB == n: return True

%o elif polyB > n: return False

%o return False

%o print([k for k in range(10**4) if ok(k)]) # _Michael S. Branicky_, Aug 10 2022

%Y Cf. A054841, A054842, A067255, A104244, A167221.

%Y A206284 describes the polynomial encoding used here.

%K nonn

%O 1,1

%A _Ctibor O. Zizka_, Oct 30 2009

%E Edited by _Jon E. Schoenfield_, Mar 16 2022

%E Incorrect term 71 removed, new name and more terms from _Michel Marcus_, Aug 08 2022

%E a(41)-a(46) from _Michael S. Branicky_, Aug 10 2022