Project Euler Forum

Greetings. I THOUGHT that problem 111 would be rather easy. Unfortunately, I'm coming up with the incorrect answer (530414267192) and have NO idea what the issue must be.

This is the problem in which we try to find the primes with the maximum number of repeated digits for each digit. For instance, for four digits, there exists at least one prime such that there are three 1's in it. In fact, there are nine of them. So the M(4,1) = 3 since there is a maximum of three 1's (1111 is not prime), and N(4,1) = 9 since there are nine such primes. The problem, essentially, is to find all M(10,d) and N(10,d) (yes, the problem is actually to sum them, but if you can find them, then summing them should be relatively easy, and I don't want to give too much away if others are having problems with it). Can someone verify the following table?

Thanks!



Nandor

ps. If the below table IS too much information to post here, please let me know.


[tt]d M(10,d) N(10,d)
-------------------------------
0 8 8
1 9 11
2 8 34
3 9 7
4 9 1
5 9 1
6 9 1
7 9 9
8 8 24
9 9 8[/tt]

Your values for M(10,d) seem correct. Your values for N(10,d) are mostly correct. I get higher values for d=2 and d=8. Are you sure you are checking all combinations for the remaining two digits? (I think you exclude some non-leading zero's, but why should you do that ?)

Thanks, harryh, that's precisely what the issue was. Don't quite know how I missed that one!

I get the same values for M(10,d) and N(10,d) as Nandor except the following. anybody know where I might be going wrong? are these too high or too low? Thanks for any help.

jake223 wrote:I get the same values for M(10,d) and N(10,d) as Nandor except the following. anybody know where I might be going wrong? are these too high or too low?

Too high. You're either counting some numbers multiple times or counting some which are not prime or fail the other criteria.

Thanks. I figured out I was counting most of them twice and allowing leading zeroes on 2s, not 8s. Solved it now

Obviously I cannot find the right answer for problem 111.
I am a little desperate, can anyone give me some hint, what is wrong with my results?
My results are:
Sum primes found digit max number

38.000.000.042 8 0 8
12.882.626.601 11 1 9
118.046.935.626 48 2 8
23.234.122.821 7 3 9
4.444.444.447 1 4 9
5.555.555.557 1 5 9
6.666.666.661 1 6 9
59.950.904.793 9 7 9
374.455.893.316 42 8 8
78.455.389.922 8 9 9

721692539786 136

@Steinke, we realise that you are new here, but please don't start a new topic for a problem if there exists already one.

steinke wrote: Sum primes found digit max number

118.046.935.626 48 2 8
374.455.893.316 42 8 8

Those "primes found" counts are wrong.

thanks thundre
I eliminated some double primes for 2's and 8's.
now the result is OK

Problem 111 is titled "Primes with runs." The problem text discusses repeated digits but not uninterrupted sequences of a digit. The term "run" in the title implies uninterrupted sequences and is misleading.

For 2s I get ## primes, and for 8s I get ## primes. How far off am I?

Seven.

Thanks. Anybody else having trouble with this, check your list of primes and make sure there are no duplicates.

In my program S(4,d) comes out correctly. That's something, but surely doesn't prove a thing. Could anybody confirm that S(3,d) = *283 and S(7,d) = 1961*? [* as usual, an undefined number of digits]

Yes and no.

OP wrote:

nandor wrote:[...]

d       M(10,d)       N(10,d)
-------------------------------
0       8                8
1       9                11
2       8                34
3       9                7
4       9                1
5       9                1
6       9                1
7       9                9
8       8                24
9       9                8

Should this table be correct? I'm being quite dazzled. M(10, 0) = 8 seems trivial, but the only n for which I get M(n, d) = 9 are 4, 5, 6, 7. I've already checked factorizations of 10-digit numbers with 9 consecutive 1s for primality - and found none.

Can anyone confirm my suspicions?

Oliver1978 wrote:Should this table be correct? I'm being quite dazzled. M(10, 0) = 8 seems trivial, but the only n for which I get M(n, d) = 9 are 4, 5, 6, 7. I've already checked factorizations of 10-digit numbers with 9 consecutive 1s for primality - and found none.

I haven't checked the table, but I think I know what your issue is. The problem talks of repeated digits, whereas you mention checking for consecutive 1s.

Looking at the example in the problem, we see that 1117 has three repeated ones which are consecutive, whereas 1151 has three repeated ones which aren't consecutive, but is still valid.

I can assure you that there is at least one 10-digit prime containing nine (not necessarily consecutive) 1s.

Hmm... Shouldn't that be the matter with N? Just like in the description M(4,1) = 3, but N(4,1) = 9. A 4-digit prime has at most 3 consecutive 1s, and 9 primes having 4 digits contain 3 repeated 1s. So I figured M() is about the maximum number of consecutive digits d.