C#, 10039 28164 digits
6 0{28157} 169669
Edit: I've made another program based on Qualtagh's algorithm with some minor modifications:
- I'm searching for the numbers of the form L000...000R, where L is
left composite, R is right composite. I allowed the left composite
number L to have multiple digits, although this is mostly a stylistic
change, and it probably doesn't affect the efficiency of the
algorithm.
- I've added multithreading to speed up the search.
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Threading;
using System.Threading.Tasks;
using Mpir.NET;
class Program
{
const int PrimeNotFound = int.MaxValue;
private static BitArray _primeSieve;
private static HashSet<Tuple<int, int>> _templatesToSkip = new HashSet<Tuple<int, int>>();
static void Main(string[] args)
{
int bestDigitCount = 0;
foreach (Tuple<int, int> template in GetTemplates())
{
int left = template.Item1;
int right = template.Item2;
if (SkipTemplate(left, right))
continue;
int zeroCount = GetZeroCountOfPrime(left, right);
if (zeroCount != PrimeNotFound)
{
int digitCount = left.ToString().Length + right.ToString().Length + zeroCount;
if (digitCount >= bestDigitCount)
{
string primeStr = left + " 0{" + zeroCount + "} " + right;
Console.WriteLine("testing " + primeStr);
bool isFragile = IsFragile(left, right, zeroCount);
Console.WriteLine(primeStr + " is fragile: " + isFragile);
if (isFragile)
bestDigitCount = digitCount;
}
_templatesToSkip.Add(template);
}
}
}
private static int GetZeroCountOfPrime(int left, int right)
{
_zeroCount = 0;
int threadCount = Environment.ProcessorCount;
Task<int>[] tasks = new Task<int>[threadCount];
for (int i = 0; i < threadCount; i++)
tasks[i] = Task.Run(() => InternalGetZeroCountOfPrime(left, right));
Task.WaitAll(tasks);
return tasks.Min(task => task.Result);
}
private static int _zeroCount;
private static int InternalGetZeroCountOfPrime(int left, int right)
{
const int maxZeroCount = 40000;
int zeroCount = Interlocked.Increment(ref _zeroCount);
while (zeroCount <= maxZeroCount)
{
if (zeroCount % 1000 == 0)
Console.WriteLine("testing " + left + " 0{" + zeroCount + "} " + right);
if (IsPrime(left, right, zeroCount))
{
Interlocked.Add(ref _zeroCount, maxZeroCount);
return zeroCount;
}
else
zeroCount = Interlocked.Increment(ref _zeroCount);
}
return PrimeNotFound;
}
private static bool SkipTemplate(int left, int right)
{
for (int leftDiv = 1; leftDiv <= left; leftDiv *= 10)
for (int rightDiv = 1; rightDiv <= right; rightDiv *= 10)
if (_templatesToSkip.Contains(Tuple.Create(left / leftDiv, right % (rightDiv * 10))))
return true;
return false;
}
private static bool IsPrime(int left, int right, int zeroCount)
{
return IsPrime(left.ToString() + new string('0', zeroCount) + right.ToString());
}
private static bool IsPrime(string left, string right, int zeroCount)
{
return IsPrime(left + new string('0', zeroCount) + right);
}
private static bool IsPrime(string s)
{
using (mpz_t n = new mpz_t(s))
{
return n.IsProbablyPrimeRabinMiller(20);
}
}
private static bool IsFragile(int left, int right, int zeroCount)
{
string leftStr = left.ToString();
string rightStr = right.ToString();
for (int startIndex = 0; startIndex < leftStr.Length - 1; startIndex++)
for (int count = 1; count < leftStr.Length - startIndex; count++)
if (IsPrime(leftStr.Remove(startIndex, count), rightStr, zeroCount))
return false;
for (int startIndex = 1; startIndex < rightStr.Length; startIndex++)
for (int count = 1; count <= rightStr.Length - startIndex; count++)
if (IsPrime(leftStr, rightStr.Remove(startIndex, count), zeroCount))
return false;
return true;
}
private static IEnumerable<Tuple<int, int>> GetTemplates()
{
const int maxDigitCount = 8;
PreparePrimeSieve((int)BigInteger.Pow(10, maxDigitCount));
for (int digitCount = 2; digitCount <= maxDigitCount; digitCount++)
{
for (int leftCount = 1; leftCount < digitCount; leftCount++)
{
int rightCount = digitCount - leftCount;
int maxLeft = (int)BigInteger.Pow(10, leftCount);
int maxRight = (int)BigInteger.Pow(10, rightCount);
for (int left = maxLeft / 10; left < maxLeft; left++)
for (int right = maxRight / 10; right < maxRight; right++)
if (IsValidTemplate(left, right, leftCount, rightCount))
yield return Tuple.Create(left, right);
}
}
}
private static void PreparePrimeSieve(int limit)
{
_primeSieve = new BitArray(limit + 1, true);
_primeSieve[0] = false;
_primeSieve[1] = false;
for (int i = 2; i * i <= limit; i++)
if (_primeSieve[i])
for (int j = i * i; j <= limit; j += i)
_primeSieve[j] = false;
}
private static bool IsValidTemplate(int left, int right, int leftCount, int rightCount)
{
int rightDigit = right % 10;
if ((rightDigit != 1) && (rightDigit != 9))
return false;
if (left % 10 == 0)
return false;
if ((left + right) % 3 == 0)
return false;
if (!Coprime(left, right))
return false;
int leftDiv = 1;
for (int i = 0; i <= leftCount; i++)
{
int rightDiv = 1;
for (int j = 0; j <= rightCount; j++)
{
int combination = left / leftDiv * rightDiv + right % rightDiv;
if (_primeSieve[combination])
return false;
rightDiv *= 10;
}
leftDiv *= 10;
}
return true;
}
private static bool Coprime(int a, int b)
{
while (b != 0)
{
int t = b;
b = a % b;
a = t;
}
return a == 1;
}
}
Old answer:
8 0{5436} 4 0{4600} 1
The are a few notable patterns for fragile primes:
600..00X00..009
900..00X00..009
800..00X00..001
999..99X99..999
where X can be 1, 2, 4, 5, 7 or 8.
For such numbers we only have to consider (length - 1) possible Remove operations. The other Remove operations produce either duplicates or obviously composite numbers. I tried to search for all such numbers with up to 800 digits and noticed that 4 patterns come up more frequently than the rest: 8007001, 8004001, 9997999 and 6004009. Since Emil and Jakube are using the 999X999 pattern, I decided to use 8004001 just to add some variety.
I've added the following optimizations to the algorithm:
- I start searching from numbers with 7000 digits and then increment
length by 1500 every time a fragile prime is found. If there is no
fragile prime with a given length then I increment it by 1. 7000 and
1500 are just arbitrary numbers that seemed appropriate.
- I'm using multithreading to search for the numbers with different length at the same time.
- The result of each prime check is stored in a hash table to prevent duplicate checks.
- I'm using Miller-Rabin implementation from Mpir.NET, which is very fast (MPIR is a fork of GMP).
using System;
using System.Collections.Concurrent;
using System.Threading.Tasks;
using Mpir.NET;
class Program
{
const string _template = "8041";
private static ConcurrentDictionary<Tuple<int, int>, byte> _compositeNumbers = new ConcurrentDictionary<Tuple<int, int>, byte>();
private static ConcurrentDictionary<int, int> _leftPrimes = new ConcurrentDictionary<int, int>();
private static ConcurrentDictionary<int, int> _rightPrimes = new ConcurrentDictionary<int, int>();
static void Main(string[] args)
{
int threadCount = Environment.ProcessorCount;
Task[] tasks = new Task[threadCount];
for (int i = 0; i < threadCount; i++)
{
int index = i;
tasks[index] = Task.Run(() => SearchFragilePrimes());
}
Task.WaitAll(tasks);
}
private const int _lengthIncrement = 1500;
private static int _length = 7000;
private static object _lengthLock = new object();
private static object _consoleLock = new object();
private static void SearchFragilePrimes()
{
int length;
lock (_lengthLock)
{
_length++;
length = _length;
}
while (true)
{
lock (_consoleLock)
{
Console.WriteLine("{0:T}: length = {1}", DateTime.Now, length);
}
bool found = false;
for (int rightCount = 1; rightCount <= length - 2; rightCount++)
{
int leftCount = length - rightCount - 1;
if (IsFragilePrime(leftCount, rightCount))
{
lock (_consoleLock)
{
Console.WriteLine("{0:T}: {1} {2}{{{3}}} {4} {2}{{{5}}} {6}",
DateTime.Now, _template[0], _template[1], leftCount - 1,
_template[2], rightCount - 1, _template[3]);
}
found = true;
break;
}
}
lock (_lengthLock)
{
if (found && (_length < length + _lengthIncrement / 2))
_length += _lengthIncrement;
else
_length++;
length = _length;
}
}
}
private static bool IsFragilePrime(int leftCount, int rightCount)
{
int count;
if (_leftPrimes.TryGetValue(leftCount, out count))
if (count < rightCount)
return false;
if (_rightPrimes.TryGetValue(rightCount, out count))
if (count < leftCount)
return false;
if (!IsPrime(leftCount, rightCount))
return false;
for (int i = 0; i < leftCount; i++)
if (IsPrime(i, rightCount))
return false;
for (int i = 0; i < rightCount; i++)
if (IsPrime(leftCount, i))
return false;
return true;
}
private static bool IsPrime(int leftCount, int rightCount)
{
Tuple<int, int> tuple = Tuple.Create(leftCount, rightCount);
if (_compositeNumbers.ContainsKey(tuple))
return false;
using (mpz_t n = new mpz_t(BuildStr(leftCount, rightCount)))
{
bool result = n.IsProbablyPrimeRabinMiller(20);
if (result)
{
_leftPrimes.TryAdd(leftCount, rightCount);
_rightPrimes.TryAdd(rightCount, leftCount);
}
else
_compositeNumbers.TryAdd(tuple, 0);
return result;
}
}
private static string BuildStr(int leftCount, int rightCount)
{
char[] chars = new char[leftCount + rightCount + 1];
for (int i = 0; i < chars.Length; i++)
chars[i] = _template[1];
chars[0] = _template[0];
chars[leftCount + rightCount] = _template[3];
chars[leftCount] = _template[2];
return new string(chars);
}
}
5Even if I don't hard code the answer, I could start searching at a point very close to a large fragile prime. Obviously, nobody wants to start searching at 1. What's stopping me from doing this? Exactly how close can I start my search before I get called out for basically hard-coding the answer? I love the challenge by the way. – Rainbolt – 2014-11-19T16:40:06.240
@Rainbolt You may start searching from any number you want, but you are not allowed to use numbers found by running your program for more than 15 minutes. Obviously, I can't enforce this rule, but hopefully everyone will play fair. – Suboptimus Prime – 2014-11-19T16:47:27.970
2
@SuboptimusPrime You could instead remove the time limit altogether, because I believe at some point that will be so rare that it'll be a feat to find the next one anyway. (Similar to http://codegolf.stackexchange.com/questions/41021/find-highest-scoring-matrix-without-property-x)
– Martin Ender – 2014-11-19T16:49:01.3231Related – FryAmTheEggman – 2014-11-19T16:49:56.663
1@SuboptimusPrime Fair enough. I'm kind of leaning towards hoping everyone plays fair now, because as some folks pointed out in the chat, its been done at least twice before, and it worked. Leave it to the downvoters to beat up anyone who tries to cheat. – Rainbolt – 2014-11-19T16:53:14.877
@MartinBüttner Not everyone can keep their PC's running for hours or days, so they will be at a disadvantage if I remove the time limit. I want to make this challenge more accessible for everyone. – Suboptimus Prime – 2014-11-19T16:56:13.080
7You're still leaving at a disadvantage those who have slower computers – John Dvorak – 2014-11-19T16:57:14.930
@JanDvorak True, but I don't think I can do anything about it. That's a universal problem for all optimization challenges I guess. – Suboptimus Prime – 2014-11-19T17:00:49.200
1@SuboptimusPrime Well, you could test all submissions yourself (that's what people do for fastest-code challenges). – Martin Ender – 2014-11-19T17:18:21.457
@MartinBüttner I've based my rules on this question. If I'll test all submissions myself than other people would have to optimize their programs for my hardware, which doesn't look like a good idea to me. And I'm still unsure about that time limit rule. I'll remove it if there will be enough demand for it.
– Suboptimus Prime – 2014-11-19T17:31:19.4731I finally realized that the time limit was pointless. You could run the program repeatedly on the consecutive intervals of numbers, 15 minutes at a time. That would effectively remove the time limit without cheating, because the rules allow you to start searching from any number you want. – Suboptimus Prime – 2014-11-19T21:48:37.630
11It took me an embarrassingly long time to realize that "Write a program that finds the largest fragile prime" did not mean "There exists a largest fragile prime. Write a program that finds it." I guess I've done too much Project Euler. :-P – ruakh – 2014-11-20T06:11:08.630
"You may use probabilistic primality tests." So if I have a number
p, and2**(p-1) % p= 1, I can claimpis prime? – feersum – 2014-11-20T22:08:35.777@feersum You may use any algorithm you want but it has to produce the correct result, so it's probably better to use something more reliable than
2**(p-1) % p = 1. – Suboptimus Prime – 2014-11-21T06:43:08.333I don't get it. If the result has to be correct, how is it then OK if it may be incorrect? – feersum – 2014-11-21T06:45:45.280
@feersum I'm veryfing all the answers with a probabilistic test that has a very low possibility of error. You answer has to pass this test to be accepted. – Suboptimus Prime – 2014-11-21T06:49:43.263
1So the result need not be correct, if someone can guess which algorithm you are using ;) – feersum – 2014-11-21T06:52:11.333
@feersum I'm using 40 random miller-rabin tests as a primality test. I don't think it's possible to adjust any algorithm to pass 40 random tests :) – Suboptimus Prime – 2014-11-21T07:00:49.667