A137269 Number of primes with maximal digit product for a digit sum of n.

0, 1, 1, 2, 1, 0, 2, 1, 0, 1, 2, 0, 5, 1, 0, 4, 3, 0, 8, 2, 0, 2, 2, 0, 10, 1, 0, 5, 4, 0, 8, 1, 0, 4, 2, 0, 17, 151, 0, 7, 4, 0, 13, 3, 0, 812, 3, 0, 17, 4, 0, 12, 1, 0, 13, 1, 0, 6, 2, 0, 18, 1, 0, 11, 1000, 0, 24, 2, 0, 5, 1, 0, 25, 1, 0, 10, 2, 0, 23, 2, 0, 9, 1

Offset: 1

Author

Lekraj Beedassy, Apr 05 2008

Keywords

• nonn
• base

Comments

From Chai Wah Wu, Dec 04 2015, Nov 03 2018: (Start)

If n > 3 and n == 0 (mod 3) then a(n) = 0 since the digit sum is a multiple of 3.

Primes with digit product maximal among all numbers with the same digit sum (not just maximal among primes) only contain the digits 2, 3 or 4. A digit 0 leads to a digit product 0 which is not maximal. A digit 1 with another digit d (since 1 is not prime, there must be another digit d) can be replaced with the digit d+1 (if d < 9) which preserves the digit sum, but strictly increases the digit product (if d = 9, 1 and 9 can be replaced with 3, 3 and 4 which again increases the digit product). For a digit d > 4, there is a series of digits from the set {2,3,4} whose sum is d and whose product is strictly larger than d. For instance, 5 -> {2,3} whose product is 6. 6 -> {3,3}, 7 -> {3,4}, 8 -> {2,3,3}, 9 -> {3,3,3}. Thus the digit d in a number can be replaced with digits 2, 3, 4 to obtain a number with the same digit sum and a larger digit product. Furthermore, the digits 2 and 4 cannot both appear, the digit 2 cannot appear more than twice and the digit 4 cannot appear more than once since {3,3} also sums to 6 and has product 9 > 8.

This analysis implies the following for n > 3. If n == 1 (mod 3), then primes with maximal digit product among all numbers with the same digit sum (if they exist) have digits 3 and either two digits 2 or a single digit 4. If n == 2 (mod 3), then primes with maximal digit product among all numbers with the same digit sum (if they exist) have digits 3 and a single digit 2. Values for n for which such primes do not exist are 4, 38, 46, 65, 94, ... In these cases a(n) can still be > 0, but the digit product of these primes is not maximal among all numbers with digit sum n. So far, it seems that in these cases (except for n = 4) these primes also only contain the digits 2, 3, or 4.

(End)

Examples

			a(19)=8 and a(20)=2 because we respectively have the 8 primes 333433, 334333, 343333, 2332333, 2333323, 3223333, 3233323, 3332233 all with a maximal digit product of 3^5*2^2 = 972 for a digit sum of 19 and the 2 primes 3233333, 3333233 with maximal digit product 3^6*2 = 1458 for digit sum 20.
		

Links

• Chai Wah Wu, Table of n, a(n) for n = 1..802

Crossrefs

Cf. A000792, A133223, A136150, A137248, A138975.

Programs

Mathematica

Needs["Combinatorica`"]; Table[If[And[n > 3, Divisible[n, 3]], 0, Length@ MaximalBy[Select[FromDigits /@ Flatten[Map[Permutations, Combinatorica`Partitions@ n], 1] /. x_ /; EvenQ@ x -> Nothing, PrimeQ], Times @@ IntegerDigits@ # &]], {n, 24}] (* Michael De Vlieger, Dec 11 2015, Version 10 *)

Extensions

a(25) and a(28) corrected and a(29)-a(83) added by Chai Wah Wu, Nov 30 2015