3
$\begingroup$

Let a “number chain” be a series of numbers, $n_0, n_1, ... n_{m-1}$ for some $m$, such that in base 10 the low digits of $n_i$ match high digits of $n_{(i+1)mod m}$.

For example, after the number 123456, numbers that begin with 6, or 56, or 456, etc, are allowed.

For any given number chain $N = n_0, n_1, ... n_{m-1}$, we assign a score $S(N)$ and a length $L(N)$ as follows. Let $P(n) = +1$ if $n$ is a positive prime integer equal to exactly one of the $n_i$ values, and -5 otherwise. Let $G(n) =$ number of digits of $n$, and let $H(n) = G(n)\cdot G(n)$. Now set $S(N) = \sum\limits_{i=0}^{m-1} P(n_i)\cdot H(n_i)$, and set $L(n)$ equal to the number of characters occupied by $N$ when it is written with $n_0, n_1, ... n_{m-1}$ overlapped as much as they can be.

Examples: The chain $(730573, 573973, 973373, 730573)$ has score $S(N) = +1\cdot36\cdot2 + -5\cdot36\cdot2 = -288$ and length $L(N) = 16$ (from 7305739733730573).

The chain $(730573, 573973, 973373, 373273)$ has score $S(N) = +1\cdot36\cdot4 = 144$ and length $L(N) = 15$ (from 730573973373273).

Problem: Find a high scoring chain $N$ with $L(N) = 53$.

$\endgroup$
1
  • $\begingroup$ As another example, if the $G(n)$ values are {9,10,18,27,36,37,48,46,45,37,36,34,27,22,9,7} for a chain of 16 primes and $L(N)$=53, the score would be 15508. $\endgroup$ Aug 26, 2014 at 6:15

2 Answers 2

1
$\begingroup$

It is straightforward to test primes like those shown in Penguino's answer, but using fill digits in {1, 3, 7, 9} instead of just {1}. For example, given a prefix, a suffix, a fill digit, and two limits, the testpair procedure in the following code (chain-primes.py) makes a list of compatible primes and calculates the score for the listed primes. Here's an example of its use (within ipython environment):

In [94]: execfile('chain-primes.py')
In [95]: testpair(1234, 901, 9)
Scores  7282 + 819 = 8101
 6 123499...............................................
12 123499999999.........................................
20 12349999999999999999.................................
29 12349999999999999999999999999........................
34 1234999999999999999999999999999999...................
48 123499999999999999999999999999999999999999999999.....
49 1234999999999999999999999999999999999999999999999....
27 ..........................999999999999999999999999901
 7 ..............................................9999901
 5 ................................................99901
 4 .................................................9901

For this example, testpair used findPre to find primes (like 123499, 123499999999, etc) that begin with 1234 and end with 9*, ie an arbitrary number of 9's. Then it used findSuf to find primes (like 9901, 99901, etc) that begin with 9* and end with 901. The line Scores 7282 + 819 = 8101 indicates that the seven primes beginning with 1234 score 7282 points, and the four primes ending with 901 score 819 points. Finally, testpair used shoPre and shoSuf to display results.

I wrote additional code (not shown) that (1) calls findPre to look for high-scoring prefixes for all numbers up to some limit; (2) calls findSuf to look for high-scoring suffixes that are not multiples of two or five; (3) sorts both data sets into higher-scores-first order; (4) builds lists of chain-compatible prefixes and suffixes; and (5) computes valid scores for likely candidate pairs and displays high scores.

For prefixes and suffixes that contain at most 7 digits, the best result I've found scores 25826 points, as shown next with output from the call testpair(1349812, 198271, 9, 48). [The value of 48 for parameter plim limits prefixed primes to at most 47 digits; by contrast, the less-constrained call testpair(1349812, 198271, 9) lists a 51-digit prime whose trailing 9's overlap non-9's in the suffix area. The correct total for such a pair is less than the sum of their separate unconstrained scores.]

In [83]: testpair(1349812, 198271, 9, 48)
Scores  13338 + 12488 = 25826
 9 134981299............................................
14 13498129999999.......................................
23 13498129999999999999999..............................
32 13498129999999999999999999999999.....................
34 1349812999999999999999999999999999...................
35 13498129999999999999999999999999999..................
39 134981299999999999999999999999999999999..............
40 1349812999999999999999999999999999999999.............
41 13498129999999999999999999999999999999999............
46 1349812999999999999999999999999999999999999999.......
47 13498129999999999999999999999999999999999999999......
46 .......9999999999999999999999999999999999999999198271
45 ........999999999999999999999999999999999999999198271
44 .........99999999999999999999999999999999999999198271
37 ................9999999999999999999999999999999198271
34 ...................9999999999999999999999999999198271
31 ......................9999999999999999999999999198271
30 .......................999999999999999999999999198271
28 .........................9999999999999999999999198271
25 ............................9999999999999999999198271
16 .....................................9999999999198271
14 .......................................99999999198271
10 ...........................................9999198271
 8 .............................................99198271

Here is the chain-primes.py code:

from gmpy import next_prime, numdigits, is_prime

def digitcount(b):
    nd = numdigits(b)           # May be off-by-one
    while 10**nd    <= b:  nd += 1
    while 10**(nd-1) > b:  nd -= 1
    return nd

def findPre(pre, lim, d):
    b, s, p, preDig = pre, 0, [], digitcount(pre) 
    fillLim = lim-preDig
    for i in range(fillLim):
        if is_prime(b):
            s += (preDig+i)**2
            p.append(i)
        b = 10*b + d
    return s, pre, p

def findSuf(suf, lim, d):
    b, s, p, preDig = suf, 0, [], digitcount(suf)
    fillLim = lim-preDig
    k = d * (10**preDig)      # Eg if b is 37 and d is 7, now k=700.
    for i in range(fillLim):
        if is_prime(b):
            s += (preDig+i)**2
            p.append(i)
        b += k;  k *= 10;
    return s, suf, p

def shoPre(preSet, lim, d):
    sco, pre, llist = preSet
    pdig = digitcount(pre)
    for l in llist:
        print '{:2} {:.<53}'.format(pdig+l, repr(pre) + repr(d)*l)

def shoSuf(sufSet, lim, d):
    sco, suf, llist = sufSet
    sdig = digitcount(suf)
    for l in reversed(llist):
        print '{:2} {:.>53}'.format(sdig+l, repr(d)*l + repr(suf))

def testpair(pre, suf, filld, plim=53, slim=53):
    preSet = findPre(pre, plim, filld)
    sufSet = findSuf(suf, slim, filld)
    print 'Scores  {} + {} = {}'.format(
        preSet[0], sufSet[0], preSet[0]+sufSet[0])
    shoPre(preSet, plim, filld)
    shoSuf(sufSet, slim, filld)
$\endgroup$
0
$\begingroup$

Corrected: I believe the number chain N = (n0,n1) where:

 n0=32711111111111111111111111111111111111111111111111, and
 n1=11111111111111111111111111111111111111111111111153 

has a fairly high score.

The low 47 digits of n0 '11111111111111111111111111111111111111111111111' match the high 47 digits of n1, and the low 1st digit of n1 '3' matches the high 1st digit of n0, so I believe this is now a valid chain.

The two numbers overlap to form the 53 digit number

 N=32711111111111111111111111111111111111111111111111153

with length 53,

Both numbers are prime (according to a Miller-Rabin test), so P(n0) = P(n1) = 1 Both numbers are 50 digits long so G(n0) = G(n1) = 50 and H(n0) = H(n1) = 50^2 = 2500

So S(N) = Sum(P(n0).H(n0),P(n1).H(n1)) = 1*2500 + 1*2500 = 5000.

It would be nice if N itself was also prime, but alas it is not (but its last two digits do equal its length).

$\endgroup$
4
  • $\begingroup$ Note that 1+1 mod 2 is 0, so the low digits of $n_1$ must match the high digits of $n_0$. Ie, the given pair is not a valid chain. $\endgroup$ Aug 26, 2014 at 3:51
  • $\begingroup$ @jwpat7 - I missed the 'mod' so didn't see the requirement for the second end match. Believe the new solution is now valid. $\endgroup$
    – Penguino
    Aug 26, 2014 at 5:04
  • $\begingroup$ Yes. Also, 3271, 3271111, 3271111111111, 11111111111111111111111111111111111153, 11111111111111153, 1111111111111153, 1111111111153, 11111111153, 1153, and 53 can be put into that chain $\endgroup$ Aug 26, 2014 at 6:06
  • $\begingroup$ Ah - clever. I hadn't noticed that. Certainly increases S(N) significantly. $\endgroup$
    – Penguino
    Aug 26, 2014 at 21:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.