login
Largest prime obtained by concatenation of parts of a distinct partition of n. 0 if no such number exist.
1

%I #21 Sep 08 2024 08:26:41

%S 0,2,3,31,41,0,421,521,0,4231,5231,0,7321,8231,0,64231,74231,0,94321,

%T 431021,0,754123,854213,0,5431021,6421013,0,8431021,9431021,0,

%U 65412103,75411023,0,95421103,96412103,0,643110211,765324101,0,965421013,975431021,0,7542103111,8543121011

%N Largest prime obtained by concatenation of parts of a distinct partition of n. 0 if no such number exist.

%C Conjecture a(n) = 0 only for n = 1, or n == 0 (mod 3), n is > 3. Subsidiary sequence (hard): Number of primes generated by concatenation of distinct partitions of n.

%H Michael S. Branicky, <a href="/A110456/b110456.txt">Table of n, a(n) for n = 1..93</a>

%H Michael S. Branicky, <a href="/A110456/a110456.txt">Python program</a>

%e Distinct partitions of 10 are (10), (9,1), (8,2), (7,3), (6,4), (7,2,1), (6,3,1), (5,3,2), (5,4,1), (4,3,2,1). a(10) = 4231 is the largest prime obtained as a concatenation of (4,2,3,1).

%o (PARI) a(n) = my(best=0, cur); forpart(u=n, if(#Set(u)==#u, forperm(u, v, cur=eval(concat(apply(x->Str(x), Vec(v)))); if(isprime(cur), best=max(best, cur))))); best \\ _Jason Yuen_, Sep 05 2024

%o (Python) # see link for faster version

%o from itertools import permutations

%o from gmpy2 import digits, is_prime, mpz

%o def dparts(n, high=0): # distinct partitions of n with terms > high

%o if n > high: yield (n,)

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

%o yield from ((i,)+p for p in dparts(n-i, i))

%o def a(n):

%o return max((int(t) for dp in dparts(n) for p in permutations(list(map(str, dp))) if is_prime(t:=mpz("".join(p)))), default=0)

%o print([a(n) for n in range(1, 41)]) # _Michael S. Branicky_, Sep 07 2024

%K base,nonn

%O 1,2

%A _Amarnath Murthy_, Aug 04 2005

%E Corrected and extended by _R. J. Mathar_, Feb 08 2008

%E a(39) and beyond from _Michael S. Branicky_, Sep 07 2024