text:
Find the largest prime whose length, sum and product is prime
The number 113 is the first prime whose length 3 is prime, digital sum 5 = 1 + 1 + 3 is prime, and digital product 3 = 1 * 1 * 3 is prime.
A prime that has these 3 properties will be called supremely prime. The primes 11117 and 1111151 are other examples.
Goal
Write a program that can find the largest supremely prime number possible in less than an hour on a decent modern personal computer (such as the preferred spec here).
You should not simply give us a large supreme prime. You need to show us your search process with code that actually works. You can build on your or other people's solutions but be sure to give them credit. We're kind of communally trying to find the largest supreme prime realizable on a normal computer in an hour.
Scoring
The submission that finds the largest supreme prime wins. If it turns out that there are finitely many supreme primes then the first submission that generates the highest supreme prime wins.
(If you can mathematically prove that either there are or aren't infinitely many supreme primes I'll give you 200 bounty rep just because. :) )
Details

You may use any source to generate your primes (e.g. internet).

You may use probabilistic prime testing methods.

Everything is in base 10.

Zero and one are NOT considered prime.

Primes that contain 0 have a digital product of 0 so obviously they can't be supreme.

To keep the page less cluttered put large (100+ digit) supreme primes in the form:
  {[number of 1's before the prime digit]}[prime digit]{[number of 1's after the prime digit]}

So 1111151 could be expressed as {5}5{1}.

Can we start with a list of primes, or fetch a list from the internet, and spend the hour doing supremeness checks?

@Sparr Yes, you can get your primes from anywhere.

Can we start with the largest known supreme prime? Personally,  that would allow a lazy person to benefit from the machine hours of others.  That said, do we have to check all primes from 2 upwards?

@DavidCarraher That's true but I think I will allow starting at the highest known supreme prime. Presumably the person who generated it will already have tried to look higher.

If you can start with the highest known supreme prime then this becomes a challenge for who can write a program that spends exactly an hour spanning the largest possible gap between two supreme primes. :(

@Sparr Maybe but I'm not sure how else to structure it. Forcing searching one at a time from 2 would not get very far since vast ranges (e.g. 10^8 to 10^10) are clearly not supreme. This way the people with the better searching algorithms should rise to the top.

Next to not containing a 0, any potential supreme prime must obviously be of the form 1^n[3|5|7]1^m, i.e. some 1s, any prime below 10 and some more 1s. There are more constraints you can put on it right away.

@Ingo Bürk - There's probably a few dumb tricks in here to eliminate a few tests.

I'm hard coding a lower limit based on where I've already searched. I can remove that if necessary.

Just to be clear, are we not allowed to skip any primes? E.g., find all supreme primes after in a given range? If so, that should made much more clear, and the challenge rephrased.

@isaacg You can skip primes and have limits. The main point is to optimize how you are searching and show the results.

If you allow to skip primes, it becomes a test of how fast you can test for prime, as you just need to start at any prime number and add a leading 1 to it. The product will be the prime and the sum will be leadingOnes + prime. All thats left is checking for prime.

Ryan has started a related question on MSE as to the existence of infinitely many supreme primes. If you've any insights for that question, please weigh in!

@Semiclassical thanks for sharing the link.

I think a proof of the existence of infinite of these supremely primes, hinges on the twin prime conjecture... I highly doubt anyone will be able to form a proof.

Isn't the first prime that fits the criteria 11?

@nmtoken 1*1 = 1 is not prime.

I can easily show that there is not currently a proof of an infinite number of supreme primes (and that a substantial amount of work has gone towards it). According to http://michaelnielsen.org/polymath1/index.php?title=Bounded_gaps_between_primes, we know that primes come along infinitely with gaps as small as 246, but for a proof of infinite supreme primes, we need a gap of 2, 4, or 6 (corresponding to the primes with a 3, 5, or 7 somewhere in them).

@TimS. I guess it is a coincidence that the gap sizes usable for this challenge happens to be the digits of the smallest proven gap size.

Perl, 15101 digits, {83}7{15017}, 8 minutes.  Max found: 72227 digits
Using my module Math::Prime::Util and its GMP back end.  It has a number of compositeness tests including is_prob_prime() with an ES BPSW test (slightly more stringent than Pari's ispseudoprime), is_prime() which adds one random-base M-R, and is_provable_prime() which will run BLS75 T5 or ECPP.  At these sizes and types, doing a proof is going to take a long time.  I threw in another M-R test in the pedantic verifier sub.  Times on a Core2 E7500 which is definitely not my fastest computer (it takes 2.5 minutes on my i7-4770K).
As Tim S. points out, we could keep searching for larger values, up to the point where a single test takes an hour.  At ~15000 digits on this E7500 it takes about 26s for an M-R test and 2 minutes for the full is_prime (trial division plus base-2 M-R plus ES Lucas plus one random-base M-R).  My i7-4770K is over 3x faster.  I tried a few sizes, mainly seeing how it did on other people's results.  I tried 8k, 20k, and 16k, killing each after ~5 minutes.  I then tried 15k in progression for ~10m each and got lucky on the 4th one.
OpenPFGW's PRP tests are certainly faster once past 4000 or so digits, and much faster indeed in the 50k+ range.  Its test has a fair amount of false positives however, which makes it a great pre-test but one would still like to verify the results with something else.
This could be parallelized with perl threads or using MCE similar to the parallel Fibonacci prime finder examples in the module.
Timing and results on an idle i7-4770K using single core:

input 3000, 16 seconds, 3019 digits, {318}5{2700}
input 4000, 47 seconds, 4001 digits, {393}7{3607}
input 4100, 5 seconds, 4127 digits, {29}7{4097}
input 6217, 5 seconds, 6217 digits, {23}5{6193}
input 6500, 5 minutes, 6547 digits, {598}5{5948}
input 7000, 15 minutes, 7013 digits, {2411}7{4601}
input 9000, 11 minutes, 9001 digits, {952}7{8048}
input 12000, 10 minutes, 12007 digits, {652}5{11354}
input 15100, 2.5 minutes, 15101 digits, {83}7{15017}
input 24600, 47 minutes, 24671 digits, {621}7{24049}
input 32060, 18 minutes, 32063 digits, {83}7{31979}
input 57000, 39 minutes, 57037 digits, {112}5{56924}
input 72225, 42 minutes, 72227 digits, {16}3{72210}

For the 32k digit result, I started 6 scripts running at the same time each with successive arguments starting at 32000.  After 26.5 minutes one finished with the 32063 digit result shown.  For 57k I let successive scripts run 6 at a time for an hour in input increments of 500 until the 57k result returned in 57 minutes.  The 72k digit result was found by doing successive primes from 70k up, so definitely not found in an hour (though once you know where to start, it is).
The script:
#!/usr/bin/env perl
use warnings;
use strict;
use Math::Prime::Util qw/:all/;
use Math::Prime::Util::GMP;  # Just to ensure it is used.

my $l = shift || 1000;  $l--;

while (1) {
  $l = next_prime($l);
  my @D = grep { is_prime($l-1 + $_) } (3,5,7);
  next unless scalar @D > 0;
  for my $s (0 .. $l-1) {
    my $e = $l-$s-1;
    warn "   checking $l $s\n" unless $s % 100;
    for my $d (@D) {
      my $n = "1"x$s . $d . "1"x$e;
      die unless length($n) == $l;
      verify_supreme($n,$s,$d,$e) if is_prime($n);  # ES BPSW + 1 rand-base M-R
    }
  }
}
sub verify_supreme {  # Be pedantic and verify the result
  my($n,$s,$d,$e) = @_;
  die "Incorrect length" unless is_prime(length($n));
  die "Incorrect sum" unless is_prime(vecsum(split(//,$n)));
  my $prod = 1; $prod *= $_ for split(//,$n);
  die "Incorrect product" unless is_prime($prod);
  die "n is not a prime!" unless miller_rabin_random($n,1);  # One more M-R test
  die "{$s} $d {$e}\n";
}

+1 for introducing me to this library! Timings on my machine to iterate primes less than 10^7 (compared to CPython with gmpy2, and PyPy with my_math): http://codepad.org/aSzc0esT

Glad you like it!  There are other ways including forprimes { ...do stuff... } 1e7; which is 10x or more faster (kudos to Pari/GP for lots of great ideas).  I always appreciate feedback so let me know if something isn't working the way you'd like.

Python 2.7 on PyPy, {2404}3{1596} (~10^4000)
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111113111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

Found this one about 50 minutes after starting from 4000. Therefore, I would estimate this is the upper limit of this code approach.
Change: I've noticed that some lengths seem to be more fruitful for generating this sort of prime than others, so I've decided to only check 50 random locations of the digit that isn't 1 instead of all possible locations, before moving on. I'm not completely sure this will improve performance, or that 50 is correct, but we'll see.
Possibilities list is generated based on the fact that for the products requirement to be fulfilled, the number must be all ones except for a prime. In addition, the prime can't be 2 because of the sum and length relationship, and the digital sum must not be divisible by three, giving the %3 requirements.
is_prime taken from http://codepad.org/KtXsydxK , written by @primo
Note: this is_prime function is actually a Baillie-PSW pseudoprime test, but there are no known counter-examples, so I'm not going to worry about the distinction.
#http://codepad.org/KtXsydxK
from my_math import is_prime
import time,random
LLIMIT=2748
time.clock()
start_time=time.time()
checked=0
while time.time()-start_time<3600:
    small_primes = [a for a in range(LLIMIT,2*LLIMIT) if is_prime(a)]
    leng,dig=(0,0)
    for a in small_primes:
        if a+2 in small_primes:
            leng,dig=(a,3)
            break
        if a+4 in small_primes:
            leng,dig=(a,5)
            break
        if a+6 in small_primes:
            leng,dig=(a,7)
            break
    start=time.clock()
    print leng,dig,time.clock(),checked
    for loc in random.sample(range(leng),50):
        checked+=1
        if is_prime(int('1'*loc+str(dig)+'1'*(leng-loc-1))):
            print leng-1,loc,dig,time.clock(),time.clock()-start, \
                  int('1'*loc+str(dig)+'1'*(leng-loc-1))
            break
    LLIMIT=leng+1

I know nothing more than the link, unfortunately. I found the link here: http://codegolf.stackexchange.com/questions/10739/find-largest-prime-which-is-still-a-prime-after-digit-deletion?rq=1 First answer

Well, then. I'll credit you.

Your is_prime() function should really be called is_probably_prime(). Actually proving that this number is prime would take a lot longer than one minute, I think.

@squeamishossifrage Technically, you're correct. I'm using the Baillie-PSW primality test, which is probabilistic but has no known failiures. I think it's close enough to a proof that I won't worry about it. I strongly doubt I'll happen to run across the first point of failure ever by chance. In addition, I'm pretty sure my candidates could be verified in under an hour if necessary.

In case anyone's interested, the 5's in the 5th row, 21st from the right.

It's like an ASCII where's wally...

Maybe you should rename the function is_very_very_very_very_very_very_very_probably_prime()...

Mathmatica and Maple both use the same method, so it can't be all that bad.

@isaacg Using a probabilistic primes method is ok. According to Wikipedia you'd get $620 for finding a counterexample and I don't want to discourage that :P (http://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_test)

@Calvin'sHobbies Thanks for the clarification. Consider putting it in the question statement for future answerers.

I'd like to point out that the isqrt function in the my_math library is flawed. If you intend to use this library for other purposes, please replace it with this: http://codepad.org/ddMR4jb5 which is correct, uses a much better seed, and runs about twice as fast on average.

PARI/GP, 4127 digits
(104127-1)/9 + 2*10515
This is a fairly straightforward search: check only prime digit lengths, then compute the possible primes to use, then iterate through all possibilities. I special-cased the common cases where there are 0 or 1 suitable prime digits to use.
supreme(lim,startAt=3)={
    forprime(d=startAt,lim,
        my(N=10^d\9, P=select(p->isprime(d+p),[1,2,4,6]), D, n=1);
        if(#P==0, next);
        if(#P==1,
            for(i=0,d-1,
                if (ispseudoprime(D=N+n*P[1]), print(D));
                n*=10
            );
            next
        );
        D=vector(#P-1,i,P[i+1]-P[i]);
        for(i=0,d-1,
            forstep(k=N+n*P[1],N+n*P[#P],n*D,
                if (ispseudoprime(k), print(k))
            );
            n*=10
        )
    )
};
supreme(4200, 4100)

This took 36 minutes to compute on one core of a fairly old machine. It would have no trouble finding such a prime over 5000 digits in an hour, I'm sure, but I'm also impatient.
A better solution would be to use any reasonable language to do everything but the innermost loop, then construct an abc file for primeform which is optimized for that particular sort of calculation. This should be able to push the calculation up to at least 10,000 digits.
Edit: I implemented the hybrid solution described above, but on my old machine I can't find the first term with >= 10,000 digits in less than an hour. Unless I run it on something faster I'll have to change to a less lofty target.

How did you know to start at 4100?

@isaacg: I was just trying to be larger than the (incorrect) Mathematica solution, which was just over 4000. I just went to the next multiple of 100 as a 'nothing-up-my-sleeve' number. Actually it seems that this was an unfortunate starting place, since I had to go longer than I expected (and longer than Mathematica!) to find a prime.

No, actually, you were incredibly lucky. (4127,3) is the first pair after 4100, and by pure chance it happens to have a prime. A lot of pairs have no prime at all.

@isaacg: Maybe so. My heuristics are clearly off, since I would have expected probability ~80% to find a prime in a given pair: 1 - exp(-15/(4*log 10)), but they seem to be rarer than that, so they don't act like random {2, 3, 5}-smooth numbers of their size (unless I goofed the calculation).

@isaacg: In any case I'm working on the "better solution" I mentioned now: pushing the hard work to pfgw. It's searched the first 20 pairs above 10^10000 without finding anything but that only took ~15 minutes.

That's some impressive speed. The solution you posted above is about 50% slower than my solution, for comparison.

@isaacg: Slow computer, slight efficiency loss to interpreting the GP code, not the greatest algorithms for big numbers (esp. since it's 32-bit not 64). I get to avoid #2 and #3 with the pfgw code. We'll see if I bit off more than I can chew with 10,000.

You can probably outsource the run to a faster computer by posting it here - I'd try, but I'm not sure my computer is that fast either.

@isaacg: I'll do that once I've found a prime with the new code. I wouldn't feel right posting an answer without results.

Mathematica  3181 digits
Update: There were some serious  mistakes in my first submission.
I was able to devote some time to checking the results for this one.
The output is formatted as a list of digits. That makes for easy checking of each of the conditions.
f[primeDigitLength_]:=
Module[{id=ConstantArray[1,primeDigitLength-1]},
permutations=Reverse@Sort@Flatten[Table[Insert[id,#,pos],{pos,primeDigitLength}]&/@{3,5,7},1];
Flatten[Select[permutations,PrimeQ[FromDigits[#]]\[And]PrimeQ[Plus@@#]&,1],1]]

Example
This was my first test, a search for a solution with 3181 digits.
It found the first case in 26 seconds.
Let's go through the reasoning.  Then we'll step into the program itself.
Let's start, as I did, "What is the 450th prime?"   Can we find a solution with that many digits (3181)?
primeDigits = Prime[450]

3181

The number is found by joining the digits.
number = FromDigits[digits];

But rather than display it, we can ask instead what the digits are and where they lie.
DigitCount[number]

{3180, 0, 0, 0, 0, 0, 1, 0, 0, 0}

This means that there were 3180 instances of the digit 1, and a single instance of the digit 7.
At what position is the digit 7?
Position[digits, 7][[1, 1]]

142

So the digit 7 is the 142nd digit. All the others are 1's.

Of course, the product of the digits must be a prime, namely 7.
digitProduct = Times @@ digits

7

And the sum of the digits is also a prime.
digitSum = Plus @@ digits
PrimeQ[digitSum]

3187
True

And we know that the number of digits is a prime.  Remember, we selected the 450th prime, namely 3118.
So all the conditions have been met.

If I am not mistaken, its sum is 4009 which is not prime.

One thing : shouldn't it be the sum of all the digits that is prime and not the number of digits? In your case you would have to test 4002 * 1 + 7 = 4009 and not 4003 according to the spec.

@Johnride: Both should be prime.

@gerw Is right. The number of digits AND the sum of the digits AND the product of digits all have to be prime.

You all were correct. In my earlier submission I forgot to check the digit sum for primality.  This is now done by seeing whether one of the following (it doesn't matter which) is prime: digit length+2, digit length _4, or digit Length +6.

That should read +4, not _4.

Python 2.7, 6217 digits: {23}5{6193} 6 mins 51 secs
I was working on my own version and was disappointed to see that @issacg had beaten me to the punch with a very similar approach, albeit with is_(very_probably)_prime(). However, I see that I have some significant differences that result in a better answer in less time (when I also use is_prime). To make this clear, when also starting from 4000, I arrive at a better 4001 digit answer ({393}7{3607}) in only 26 mins, 37 seconds using the standard Python interpreter (also at version 2.7), not the PyPy version. Also, I'm not 'spot' checking the numbers. All of the candidates are checked.
Here's the primary improvements:

Use a prime generator (https://stackoverflow.com/questions/567222/simple-prime-generator-in-python/568618#568618) to create a list of primes to check against and (his version of "small primes") and for generating eligible number lengths.

We want to spend our time looking for the largest supreme prime of a given length, not the smallest, so, I construct the largest possible numbers first for checking, not the smallest. Then, once one is found, we can immediately move on to the next length.

EDIT: Now with multiprocessing
This is a significant change to previous versions. Before, I noticed that my 8-core machine was hardly working, so, I decided to try my hand at multiprocessing in Python (first time). The results are very nice!
In this version, 7 children processes are spawned, which grab a 'task' off a queue of potential possibilities (num_length + eligible digits). They churn through trying different [7,5,3] positions until it finds one. If it does, informs the master process of the new longest length that has been found. If children are working on a num_length that is shorter, they just bail, and go get the next length.
I started this run with 6000, and it is still running, but so far, I'm very pleased with the results.
The program doesn't yet stop correctly, but not a huge deal to me.
Now the code:
#!/usr/bin/env python
from __future__ import print_function

import sys
from multiprocessing import Pool, cpu_count, Value
from datetime import datetime, timedelta

# is_prime() et al from: http://codepad.org/KtXsydxK - omitted for brevity
# gen_primes() from: https://stackoverflow.com/questions/567222/simple-prime-generator-in-python/568618#568618 - ommitted for brevity
from external_sources import is_prime, gen_primes

def gen_tasks(start_length):
    """
    A generator that produces a stream of eligible number lengths and digits
    """
    for num_length in gen_primes():
        if num_length < start_length:
            continue

        ns = [ n for n in [7,5,3] if num_length + n - 1 in prime_list ]
        if ns:
            yield (num_length, ns)

def hunt(num_length, ns):
    """
    Given the num_length and list of eligible digits to try, build combinations
    to try, and try them.
    """

    if datetime.now() > end_time or num_length <= largest.value:
        return

    print('Tasked with: {0}, {1}'.format(num_length, ns))
    sys.stdout.flush()
    template = list('1' * num_length)
    for offset in range(num_length):
        for n in ns:
            if datetime.now() > end_time or num_length <= largest.value:
                return

            num_list = template[:]
            num_list[offset] = str(n)
            num = int(''.join(num_list))

            if is_prime(num):
                elapsed = datetime.now() - start_time
                largest.value = num_length
                print('\n{0} - "{1}"\a'.format(elapsed, num))

if __name__ == '__main__':
    start_time = datetime.now()
    end_time = start_time + timedelta(seconds=3600)

    print('Starting @ {0}, will stop @ {1}'.format(start_time, end_time))

    start_length = int(sys.argv[1])

    #
    # Just create a list of primes for checking. Up to 20006 will cover the first
    # 20,000 digits of solutions
    #
    prime_list = []
    for prime in gen_primes():
        prime_list.append(prime)
        if prime > 20006:
            break;
    print('prime_list is primed.')

    largest = Value('d', 0)

    task_generator = gen_tasks(start_length)

    cores = cpu_count()
    print('Number of cores: {0}'.format(cores))

    #
    # We reduce the number of cores by 1 because __main__ is another process
    #
    pool = Pool(processes=cores - 1)

    while datetime.now() < end_time:
        pool.apply_async(hunt, next(task_generator))

it would read more cleanly if you represent the codepad link as a [broken, if necessary] import

I think that would be confusing, as the code at the other end isn't really importable like that.

use isaacg's syntax. comment the URL, then import from a nonexistent package (my_math, in his case)

Actually, I generate the numbers from largest to smallest, too. I don't think our code differences are very significant. I'd expect the difference to lie more in our computers than our code. Nevertheless, well done, and welcome to the site.

my_math can also be used to generate a list of primes, à la while prime < 20006: prime = next_prime(prime). Seems to be about 3 times as fast as gen_primes, and far more memory efficient.

@sparr, updated as per request

Excellent! You've taken the lead, and deservedly so. Also, you might want to try out PyPy - could give you another facter of 2 or so.

C, GMP - {7224}5{564} = 7789
Kudos to @issacg and all of you guys for the inspirations and tricks.
And also the masterful question asker @Calvin's Hobbies for this question.
Compile:
gcc -I/usr/local/include -o p_out p.c -pthread -L/usr/local/lib -lgmp

If you feel like donating your computation power or curious of the performance, feel free copy the code and compile. ;) You will need GMP installed.
#include<stdio.h>
#include<stdlib.h>
#include<sys/time.h>
#include<gmp.h>
#include<pthread.h>

#define THREAD_COUNT 1
#define MAX_DIGITS   7800
#define MIN_DIGITS   1000

static void huntSupremePrime(int startIndex) {

    char digits[MAX_DIGITS + 1];

    for (int i = 0; i < MAX_DIGITS; digits[i++] = '1');

    digits[MAX_DIGITS] = '\0';
    mpz_t testPrime, digitSum, digitCount, increment;

    for (int j = 0; j < MAX_DIGITS - startIndex; digits[j++] = '0');

    int step = THREAD_COUNT * 2;

    for (int i = startIndex, l = MAX_DIGITS - startIndex; i > MIN_DIGITS - 1;
        i -= step, l += step) {
        fprintf(stderr, "Testing for %d digits.\n", i);
        mpz_init_set_ui(digitCount, i);
        if (mpz_millerrabin(digitCount, 10)) {
            for (int j = 3; j < 8; j += 2) {
                mpz_init_set_ui(digitSum, i - 1 + j);
                if (mpz_millerrabin(digitSum, 10)) {
                    gmp_printf("%Zd \n", digitSum);
                    digits[MAX_DIGITS - 1] = j + 48;
                    mpz_init_set_str(testPrime, digits, 10);
                    mpz_init_set_ui(increment, (j - 1) * 99);
                    for (int k = 0; k < i/20; ++k) {
                        if (mpz_millerrabin(testPrime, 25)) {
                            i = 0;
                            j = 9;
                            k = l;
                            gmp_printf("%Zd\n", testPrime);
                            break;
                        }
                        mpz_add(testPrime, testPrime, increment);
                        mpz_mul_ui(increment, increment, 100);
                        fprintf(stderr, "TICK %d\n", k);
                    }

                }
            }
        }
        for (int j = 0; j < step; digits[l + j++] = '0');

    }
}

static void *huntSupremePrimeThread(void *p) {
    int* startIndex = (int*) p;
    huntSupremePrime(*startIndex);
    pthread_exit(NULL);
}

int main(int argc, char *argv[]) {

    int  startIndexes[THREAD_COUNT];
    pthread_t threads[THREAD_COUNT];

    int startIndex = MAX_DIGITS;
    for (int i = 0; i < THREAD_COUNT; ++i) {
        for (;startIndex % 2 == 0; --startIndex);
        startIndexes[i] = startIndex;
        int rc = pthread_create(&threads[i], NULL, huntSupremePrimeThread, (void*)&startIndexes[i]);
        if (rc) {
            printf("ERROR; return code from pthread_create() is %d\n", rc);
            exit(-1);
        }
        --startIndex;
    }

    for (int i = 0; i < THREAD_COUNT; ++i) {
        void * status;
        int rc = pthread_join(threads[i], &status);
        if (rc) {
            printf("ERROR: return code from pthread_join() is %d\n", rc);
            exit(-1);
        }
    }

    pthread_exit(NULL);
    return 0;
}

PFGW, 6067 digits, {5956}7{110}
Run PFGW with the following input file and -f100 to prefactor the numbers. In about 2-3 CPU minutes on my computer (i5 Haswell), it finds the PRP (10^(6073-6)-1)/9+6*10^110, or {5956}7{110}. I chose 6000 digits as the starting point as a nothing-up-my-sleeve number that's a little higher than all previous submissions.
ABC2 $a-$b & (10^($a-$b)-1)/9+$b*10^$c
a: primes from 6000 to 6200
b: in { 2 4 6 }
c: from 0 to 5990

Based on how quickly I was able to find this one, I could easily bump up the number of digits and still find a PRP within an hour. With how the rules are written, I might even just find the size where my CPU, running on all 4 cores, can finish one PRP test in an hour, take a long time to find a PRP, and have my "search" consist solely of the one PRP.
P.S. In some senses, this isn't a "code" solution because I didn't write anything besides the input file...but then, many one-line Mathematica solutions to mathematical problems could be described in the same way, as could using a library that does the hard work for you. In reality, I think it's hard to draw a good line between the two. If you like, I could write a script that creates the PFGW input file and calls PFGW. The script could even search in parallel, to use all 4 cores and speed up the search by ~4 times (on my CPU).
P.P.S. I think LLR can do the PRP tests for these numbers, and I'd expect it to be far faster than PFGW. A dedicated sieving program could also be better at factoring these numbers than PFGW's one-at-a-time. If you combined these, I'm sure you could push the bounds much higher than current solutions.

Python 2.7, 17-19 digits
11111111171111111

Found 5111111111111 (13 digits) in 3 seconds and this 17 digit supreme prime in 3 minutes. I'll guess that the target machine could run this and get a 19 digit supreme prime in less than an hour. This approach does not scale well because it keeps primes up to half the number of target digits in memory. 17 digit search requires storing an array of 100M booleans. 19 digits would require a 1B element array, and memory would be exhausted before getting to 23 digits. Runtime probably would be, too.
Primality test approaches that don't involve a ridiculously large array of divisor primes will fare much better.
#!/usr/bin/env python
import math
import numpy as np
import sys

max_digits = int(sys.argv[1])
max_num = 10**max_digits

print "largest supreme prime of " + str(max_digits) + " or fewer digits"

def sum_product_digits(num):
    add = 0
    mul = 1
    while num:
         add, mul, num = add + num % 10, mul * (num % 10), num / 10
    return add, mul

def primesfrom2to(n):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    """ Input n>=6, Returns a array of primes, 2 <= p < n """
    sieve = np.ones(n/3 + (n%6==2), dtype=np.bool)
    sieve[0] = False
    for i in xrange(int(n**0.5)/3+1):
        if sieve[i]:
            k=3*i+1|1
            sieve[      ((k*k)/3)      ::2*k] = False
            sieve[(k*k+4*k-2*k*(i&1))/3::2*k] = False
    return np.r_[2,3,((3*np.nonzero(sieve)[0]+1)|1)]

def checkprime(n):
    for divisor in primes:
        if (divisor>math.sqrt(n)):
            break
        if n%divisor==0:
            return False
    return True

# make an array of all primes we need to check as divisors of our max_num
primes = primesfrom2to(math.sqrt(max_num))
# only consider digit counts that are prime
for num_digits in primes:
    if num_digits > max_digits:
        break
    for ones_on_right in range(0,num_digits):
        for mid_prime in ['3','5','7']:
            # assemble a number of the form /1*[357]1*/
            candidate = int('1'*(num_digits-ones_on_right-1)+mid_prime+'1'*ones_on_right)
            # check for primeness of digit sum first digit product first
            add, mul = sum_product_digits(candidate)
            if add in primes and mul in primes:
                # check for primality next
                if checkprime(candidate):
                    # supreme prime!
                    print candidate

Mathematica  4211 4259 digits
With the number: {1042}7{3168} {388}3{3870}
Which was generated by the following code:
TimeConstrained[
 Do[
  p = Prime[n];
  curlargest = Catch[
    If[PrimeQ[p + 6],
     list = ConstantArray[1, p];
     Do[
      temp = FromDigits[ReplacePart[list, i -> 7]];
      If[PrimeQ[temp],
       Throw[temp]
       ], {i, p}]
     ];

    If[PrimeQ[p + 4],
     list = ConstantArray[1, p];
     Do[
      temp = FromDigits[ReplacePart[list, i -> 5]];
      If[PrimeQ[temp],
       Throw[temp]
       ], {i, p}]
     ];
    If[PrimeQ[p + 2],
     list = ConstantArray[1, p];
     Do[
      temp = FromDigits[ReplacePart[list, i -> 3]];
      If[PrimeQ[temp],
       Throw[temp]
       ], {i, p}]
     ];
    Throw[curlargest];
    ]

  , {n, 565, 10000}]
 , 60*60]

The throws cause it to stop testing for other numbers with the same digits as the one currently found.
since it begins testing at the most significant digit this will mean that it always returns the largest number unless the number of digits is a member of a prime triplet.
Simply started testing just below the value of one of the preceding answers :)
Once it finishes, the number is stored in the variable curlargest

JavaScript, 3019 digits, {2,273}5{745}
This uses the MillerRabin test included in BigInteger.js by Tom Wu.
Starting from 0 => 2,046 digits = {1799}7{263} in one hour.
Starting from 3000 => 3,019 digits = {2,273}5{745} in one hour, less 3 seconds.
When it started from 0, the program skipped ahead and began searching again at a length of 1.5X the length of the last s-prime found.  Then when I saw how fast it was running I guessed it would find one starting at 3000 in one hour - which it did with only 3 seconds to spare.
You can try it here: http://goo.gl/t3TmTk
(Set to calculate all s-primes, or skip ahead.)

The program works by constructing strings of all "1"s, but with one "3", "5", or "7".  I added a quick check in the IsStrPrime function to reject numbers ending in "5".
if (IsIntPrime(length)) {

    var do3s = IsIntPrime(length + 2);
    var do5s = IsIntPrime(length + 4);
    var do7s = IsIntPrime(length + 6);

    if (do3s || do5s || do7s) {

        // loop through length of number
        var before, digit, after;

        for (var after = 0; after <= length - 1; after++) {

            before = length - after - 1;
            beforeStr = Ones(before);
            afterStr = Ones(after);

            if (do3s && IsStrPrime(beforeStr + (digit = "3") + afterStr)) { RecordAnswer(); if (brk) break; }
            if (AreDone()) break;

            if (do5s && IsStrPrime(beforeStr + (digit = "5") + afterStr)) { RecordAnswer(); if (brk) break; }
            if (AreDone()) break;

            if (do7s && IsStrPrime(beforeStr + (digit = "7") + afterStr)) { RecordAnswer(); if (brk) break; }
            if (AreDone()) break;

            if (after % 10 == 0) document.title = "b=" + bestLength + ", testing=" + length + "-" + after;
        }
    }
}

This was pretty fun.  Reminds me of a puzzle I did many years back to calculate what's called a digit removed prime.  This is a prime number that if you remove any digit, then the remaining number is still prime.  For example 1037 is a digit removed prime because 1037, 037, 137, 107, and 103 are prime.  I found one 84 digits long, and the longest I know of is 332 digits long.  I'm sure we could find one much longer with the techniques used for this puzzle.  (But choosing the trial numbers is a little bit trickier - maybe?)

RE: digit removed prime, we've had that one here. 332 digits would have won, too.

Python 3.9.2, with sympy and gmpy2, 3019 digits
Completed the search from 3000 digits to 3019 digits in approximately 10 minutes on my laptop.
Port of @Charles's Pari/GP answer in Python.
import sympy
import gmpy2
import time

def supreme(lim, startAt=3):
    for d in sympy.primerange(startAt, lim + 1):
        N = 10**d // 9
        P = [p for p in [1,2,4,6] if sympy.isprime(d + p)]
        if len(P) == 0:
            continue
        if len(P) == 1:
            n = 1
            for i in range(0, d):
                if gmpy2.is_strong_bpsw_prp(N + n * P[0]):
                    print(N + n * P[0])
                n *= 10
            continue
        D = [P[i+1] - P[i] for i in range(len(P) - 1)]
        n = 1
        for i in range(0, d):
            for k in range(N + n * P[0], N + n * P[-1] + 1, n * D[0]):
                if gmpy2.is_strong_bpsw_prp(k):
                    print(k)
            n *= 10

start_time=time.time()
supreme(3019, 3000)
print(f"The search ends in {time.time()-start_time} seconds")

[encoded data, 6038 characters]
The search ends in 606.180704832077 seconds

Axiom, 3019 digits {318}5{2700}
)time on

-- Return true if n is pseudo prime else return false
-- **Can Fail**
prime1(n:PI):Boolean==
     n=1=>false
     n<4=>true
     i:=5;sq:=sqrt(1.*n)
     repeat
       if i>sq or i>50000 then break
       if n rem i=0       then return false
       i:=i+2
     if i~=50001        then return true
     --output("i")
     if powmod(3,n,n)=3 then return true
     --output("e")
     false

-- input  'n': must be n>1 prime
-- output [0] if not find any number, else return
-- [n,a,b,c,z] 'n' digits of solution,
-- 'a' number of '1', 'b' central digit, 'b' number of final digit '1'
-- 'z' the number found
g(n:PI):List NNI==
    x:=b:=z:=1
    for i in 1..n-1 repeat
        z:=z*10+1
        b:=b*10
    repeat
       --output b
       k:=0    -- 3 5 7 <-> 2 4 6
       for i in [2,4,6] repeat
           ~prime?(n+i)=>0 --somma
           k:=k+1
           t:=z+b*i
           if prime1(t) then return [n,x-1,i+1,n-x,t]
       --if x=1 then output ["k=", k]
       if k=0  then break
       x:=x+1
       b:=b quo 10
       if b<=0 then break
    [0]

-- start from number of digits n
-- and return g(i) with i prime i>=n
find(n:PI):List NNI==
    i:=n
    if i rem 2=0 then i:=i+1
    repeat
        if prime?(i) then --solo le lunghezze prime sono accettate
             output i
             a:=g(i)
             if a~=[0] then return a
        i:=i+2

result from the start value 3000 in 529 sec
(4) -> find(3000)
   3001
   3011
   3019

   (4)
   [3019, 318, 5, 2700, Omissis]
                                            Type: List NonNegativeInteger
       Time: 0.02 (IN) + 525.50 (EV) + 0.02 (OT) + 3.53 (GC) = 529.07 sec


text:
When is my piversary?
Since I want to celebrate this definitely not nerdy event, your job is to calculate the piversary (pi-anniversary) of a given date.
Input
Your code has to have a possibilty to input a date in the format DD/MM/YYYY. You can expect, that the input is valid and the year is 0000<YYYY<9996.
Output
You have to release two dates, the date in Pi months and the date in Pi years.
Rules

If your language hasn't a build in Pi, you have to make a variable which will be exact enough to calculate the dates, but it is not allowed to calculate the days separately and use fix numbers.
You have to take care, that the months have different amount of days, but you don't have to care about leap years (only if you want).
If you calculate the date, you have to add the three years/months first and then the left part in rounded days.
Your code has to accept any valid date and should be able to handle edge cases like 30/12/2000

Example:
Input: 12/04/2010

Calculate monthly piversary:
date +  3 months = 12/07/2010
date + (31*(Pi-3)) = date + 4.39 = date + 4 = 16/07/2010 //31 because July has 31 days

Calculate yearly piversary:
date + 3 years = 12/04/2013
date + (365*(Pi-3)) = date + 52 = 03/06/2013

Output:
16/07/2010,03/06/2013

May the shortest code win.

xkcd.com/1179

Are leading zeroes required in the output?

@Zaq Awesome picture :) I will use it next time, I promise.

@hsl Yes they are.

Mathematica, 152 134 bytes
f[i_]:=DateList@{i,{d="Day",m="Month",y="Year"}}~DatePlus~{{3,#},{Round[#2*(Pi-3.)],d}}~DateString~{d,"/",m,"/",y}&@@@{{m,31},{y,365}}

Ungolfed
f[i_] :=
 DateString[
    DatePlus[
     DateList@{i,{d="Day",m="Month",y="Year"}},
     {{3, #}, {Round[#2*(Pi - 3.)], d}}
    ],
    {d, "/", m, "/", y}
 ] & @@@ {{m, 31}, {y, 365}}

This does handle leap years. It's also horribly long.

MATLAB: 141 157, 169
o='DD/mm/YY'
d=datenum(x,o)
f=@(s,v) datestr(addtodate(addtodate(d,3,s),(pi-3)*v,'day'),o)
f('year',365)
f('month',eomday(year(d),month(d)))

Quite long and straightforward. It assumes the input to be in x.

Here is a version that is a few chars longer for those without the financial toolbox:
o='DD/mm/YY'
d=datenum(x,o)
[y,m]=datevec(d)
f=@(s,v) datestr(addtodate(addtodate(d,3,s),(pi-3)*v,'day'),o)
f('year',365)
f('month',eomday(y,m))

Groovy - 297 chars
Uses Joda Time. Does not handle leap years.
Golfed:
@Grab(group='joda-time', module='joda-time', version='2.3')
f=org.joda.time.format.DateTimeFormat.forPattern("dd/MM/yyyy")
t=f.parseDateTime(args[0])
p="plusDays"
m="Month"
println f.print(t."plus${m}s"(3)."$p"((t."dayOf$m"().maximumValue*(Math.PI-3)) as int))+","+f.print(t.plusYears(3)."$p"(52))

Sample run:
$ groovy Pi.groovy 12/04/2010
16/07/2010,03/06/2013

$ groovy Pi.groovy 30/12/2000
03/04/2001,20/02/2004

Ungolfed:
@Grab(group='joda-time', module='joda-time', version='2.3')

f = org.joda.time.format.DateTimeFormat.forPattern("dd/MM/yyyy")

t = f.parseDateTime(args[0])

println f.print(t.plusMonths(3).plusDays((t.dayOfMonth().maximumValue*(Math.PI-3)) as int))
        + "," +
        f.print(t.plusYears(3).plusDays(52))

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Find prime which is generating longest primes sequence using p(n+1)=(p(n)^2+1)/2
Consider following recurrence relation:
p[n + 1] = (p[n]^2 + 1) / 2

If p[1], p[2], ..., p[k] are primes and p[k+1] is not, then k is length of sequence starting with p[1].
For example, if p[1] = 3, then p[2] = 5, p[3] = 13, p[4] = 85 = 5 * 17, thus length of sequence is 3.
Goal
Write program which find number producing longest sequence you can find.
Give in your answer starting number, sequence length, source code and time in which program executes.
If multiple answers with same sequence length, then one with greater starting integer wins.
If even starting integer is same, then one with smaller executing time wins.
If you have taken starting integer for your program from another answer, then you should add its time. Picking starting integer at random is disallowed.
Winner will selected 1 week after first answer posted.

What happens if several people come up with the same number? Can you just make a brute force solution that runs infinitely?

Sure I will attempt to do this. But first provide a proof that there exists such a longest sequence.

I'm not even sure every sequence is finite...

Another good reason to treat 1 as not a prime. (1^2 + 1) / 2 = 1

@JanDvorak Seeing that this is a code-challenge, I'm pretty sure the OP is looking for the "longest sequence you can find".

@MartinBüttner Yes, I meant that way. There can be sequence of any length, I want largest you can find. However I've done some brute-force on small primes and it seems that longer sequences become more rare.

You might want to add some form of tie-breaker though in case two people do find the same maximum sequence.

I think execution time is a good tie-breaker but it needs to be specified better. a) Who is going to measure execution time? Different users use different machines and will report different times. b) Execution time for what? Once you run it, you know that you can skip the parts you've already checked.

@MartinBüttner By execution time I meant total time program spent on finding number. If you have taken starting number from another answer it will be more fair to add that's answer time. However picking starting values at random is disallowed.

Can I just make a program that prints the sequence http://oeis.org/A105318? And I do not think that we will get here any more of those numbers, because I am sure some mathematicians tried hard enough, you will have to find a sequence that is longer than the one starting at 2185103796349763249 and that is a pretty big prime...

@flawr I think it's not interesting) When writing this question, I thought up random sequence. However it seems that think up something that haven't been before is difficult...

You might be able to improve this by looking for the latest occurrence of the longest sequence. There will probably be more 6-prime sequence before that 7-prime sequence. Now these might all be known as well, but it would at least already break some ties and the answers couldn't be directly read off OEIS.

I don't think Dennis' question has been answered yet, and until it is answered it's not clear to me what you want.

@PeterTaylor The tie breakers are specified now, aren't they?

@MartinBüttner, I don't see how that answers the question about a program which loops indefinitely. And there's potential for an infinite escalation in programs which start looking at n+2 where n is the current best starting point, so the tie-breakers don't really solve the problem they aim to solve either.

@PeterTaylor I suppose the deadline does that.

@MartinBüttner, that's an awful solution. It's understandable that someone should stop updating the accepted answer when they stop frequenting the site, but as a general rule questions should not discriminate against people who come across the site in the future.

@PeterTaylor yeah, I can agree with that.

Mathematica, 66th 6-prime sequence starting at 178,308,225,421
best = {0, 0}
start = TimeUsed[];
For[i = 1, True, i++,
 p = Prime@i;
 length = 0;
 q = p;
 While[PrimeQ@q,
  ++length;
  q = (q^2 + 1)/2;
  ];
 If[length > best[[1]],
  Print[{best = {length, p}, TimeUsed[] - start}]];
 ]
best
TimeUsed[] - start

That's a fairly trivial exhaustive search. The search doesn't terminate, so you need to abort it with Alt+. after which it'll tell you how long it has run in total.
Some timings on my machine
Length    Starting Prime    Cumulative Time

4         271               0.002 s
5         169,219           0.297 s
6         356,498,179       692.1 s ~ 11.5 min

The search for 7 primes is still running. (After 110 hours I'm still an order of magnitude below the next result as given by OEIS.)
Edit: I got a moderate speed-up by ditching the lookup table.
Edit: The search has been running all night. This time I kept track of how all n-prime sequences before the first (n+1)-prime sequence. I also switched to NextPrime but I think it's actually slower - of course, I'll need it if I keep this running over the weekend.
Here is some data:
If m(n) is the number of n-prime sequences before the first (n+1)-prime sequence, then m(n) progresses like {1, 0, 4, 10, 55, >65}.
The first 5-prime sequence starts at 169,219 and took 0.3s. The last 5-prime sequence (before the 6-prime ones start) starts at 350,505,151 and took 680s to find. While the distance between two consecutive 5-prime sequences is usually on the order of 106, the two most closely spaced such sequences start at 222,193,661 and 222,266,839.
So far I've found the following 6-prime sequences:
 Starting Prime    Cumulative Time

    356,498,179       692.2 s ~  11.5 min
    432,448,789       860.1 s ~  14.5 min
  5,380,300,469    13,967.6 s ~   3.9 h
 10,667,785,241    30,519.5 s ~   8.5 h
 11,238,777,509    32,353.6 s ~   9.0 h
 12,129,977,791    35,218.5 s ~   9.8 h
 23,439,934,621    71,781.2 s ~  20.0 h
     ...  29 more ...
 95,986,224,779   304,385.  s ~  84.5 h
 99,143,377,451   314,512.  s ~  87.4 h
102,928,086,161   326,881.  s ~  90.8 h
     ...   7 more ...
125,338,612,429   398,873.  s ~ 110.8 h
     ...  18 more ...
178,308,225,421   568,694.  s ~ 158.0 h

As for the spacing of 6-prime sequences, the largest gap was about 11e9 between the 6th and 7th sequence. The two closest sequences were about 5e6 apart, the first one starting at 123,333,728,319 - they were found within 16 seconds of each other, when sometimes there is no new sequence for several hours. Also, there are 5 sequences starting between 33.99e9 and 34.9e9.
Edit: The week is over in a couple of hours, and I think 66 6-prime sequences is a good number, so I'm stopping this now.

Pretty fast you have done it) I have very similar code in Mathematica, and also found that number for 5-sequence) However they become more rare, but you have one week more to run this program)

I have suggestion. Maybe NextPrime[] can improve performance?

@user2992539 Thanks but it's actually a factor of 2 slower.

Probably it is faster with very large integers. And Prime doesn't work with integer larger than 2^42.

Probably those who found those numbers on OEIS have supercomputers or have thought up more clever algorithm.

@user2992539 Certainly the latter, but most likely both. My submission doesn't use any insight into number theory whatsoever. I'm sure if I knew more about it there would be a few trivial optimisations to speed this up a bit. I'll just leave this running until your deadline on Thursday for the fun of it, but that will still be an order of magnitude below the starting prime for the first 7-prime sequence.

There's a simple number-theoretic improvement: with the exceptions of 2, 3, and 5, all primes fall into one of 16 residue classes modulo 60. The map p->(p^2+1)/2 takes 8 of those residue classes outside the set of 16, so you only need to consider primes which equal 1, 11, 19, 29, 31, 41, 49, or 59 modulo 60.

@PeterTaylor Ah, thanks! I really need to read up on number theory at some point soon. :) I'll see how much that speeds it up.

@PeterTaylor At least up to the first couple of 6-prime sequences that didn't give any substantial savings (about 10%). But thanks, I learned something. ;)

Sage, 5 primes in 7.86 s (via Sage Notebook)
Not nearly as fast as Martin's answer, but it does work. I'm working on installing Sage onto my computer to see if it runs faster on my machine, rather than on the web.
def PrimePermutation(b):
    t = cputime()
    best = 0
    P = Primes()
    i=1
    while i<b:
        i=i+1
        q = P.next(i)
        r = q
        length = 0
        while q in P:
            length=length+1
            q = (q^2+1)/2
        if length > best:
            print(r, length, cputime() - t)
            best = length

PrimePermutation(4e10)

Returns (so far)
(3, 3, 0.0)
(271, 4, 0.009999999999990905)
(169219, 5, 7.860000000000014)

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Create a FizzBuzz compiler
Welcome to the world of compiler golf. Your task is to write a program that generates another program to play a variant of FizzBuzz on spec.
Your compiler
Write a compiler that generates variants of the FizzBuzz program to spec. The spec of this variant is expressed in the form of an array of integer/string pairs.

The input may be in any form that is convenient to your language. (My examples use n:xxxx, but this is just for illustrative purposes.)
Each integer input may only be used once per invocation of your compiler.
The integer of each pair will have a value of at least one.
The string of each pair will be made of only exactly four ASCII letters.
The output must be a single complete program that conforms to the rules below.
The output may be in any convenient form, as long as it is a textual program. (So no returning lambda expressions.)

Behavior is undefined for inputs not conforming to the above rules.
Your generated FizzBuzz program
The program generated by your compiler will take a single integer, n, as input. It will output a sequence of numbers starting from one up to and including n, replacing numbers with FizzBuzz strings when required.

The generated program must be in the same language as the compiler.
The input n may be in any form convenient to your language.
n will have a value of at least one.
A number that is a multiple of at least one of the integers input to the compiler must be replaced by all of the strings paired with those integers joined together.
A number that is not to be replaced by a FizzBuzz string must be output in decimal ASCII.

For example;
> GenFizzBuzz 3:Fizz 5:Buzz
> a.out 5
1
2
Fizz
4
Buzz

Scoring
Your entry will be scored by the length of the programs your compiler generates added to the length of your compiler. Run your compiler many times with each the following parameters and add the lengths of the generated programs together with the length of the compiler to find your score.

Just Count. (No inputs - The generated program will count 1 to n without replacements.)
Just Golf. (1:Golf - The generated program will output "Golf" n times.)
Classic FizzBuzz. (3:Fizz, 5:Buzz)

(Note that your compiler is required to generate code for any valid input, not just these listed.)

no scoring for the length of the compiler??

can we assume the integers are single digit? that there are no spaces in the strings?

@Sparr Would that (two digit integers) make a difference? Remember, its only the code generated that makes your score.

well, fizzbuzz is an already extremely thoroughly golfed problem elsewhere on the internet. I don't know if I could forget reading the solution to it if I tried.

@Sparr - You persuaded me. I've changed the rules to include the length of the compiler.

Finally a golf challenge that actually makes sense to write in AWK.

Should the compiler output to stdout or a.out?

@nyuszika7h - "The output may be in any convenient form, as long as it is a textual program."

Related: http://meta.codegolf.stackexchange.com/questions/5050/thoughts-on-compiler-golf

I assume that the generated programs must be independent and can't use the compiler in any way?

@Hjulle - I'm not sure what you mean. The text output of the first program must be a program, which may be compiled, especially if that language is normally compiled (like C et al).

I mean my own compiler program, the one that generates the fizzbuzz programs. My idea was to abuse that my compiler already existed in order to generate smaller programs (that doesn't work without access to my compiler). ;)

@Hjulle - You want your generated program to be able to call through to the compiler. Since I changed the rules to include the length of the compiler as well as the test cases, that should be okay.

Can we assume that input to the compiler is taken in order (lowest to highest or vice versa)?

Python 3 - 168 162 + 230 = 392
Oh, Python, you try so hard, but multiplying the import sys;sys.argv stuff by 4 really hurts!
import sys;a=eval(sys.argv[1])
print("import sys\nfor i in range(1,int(sys.argv[1])+1):print("+"+".join('"%s"*(i%%%d==0)'%t for t in a)+(a and"or str(i))"or"i)"))

Output programs:
import sys
for i in range(1,int(sys.argv[1])+1):print(i)
import sys
for i in range(1,int(sys.argv[1])+1):print("Golf"*(i%1==0)or str(i))
import sys
for i in range(1,int(sys.argv[1])+1):print("Fizz"*(i%3==0)+"Buzz"*(i%5==0)or str(i))

Expected input for the main program is an eval-able sequence of Python tuples or '()' for no input. (You did say "convenient".) Example input: '()', '("Golf",1),', '("Fizz",3),("Buzz",5)' Note quoting for shell and trailing comma for one input.

Fixed 1am mistake by changing from dict (undefined ordering!) to tuples.

Expected input for the other programs is just the number

In your example command line argument, I had to wrap in double quotes and use single quotes for 'Fizz' and 'Buzz' - like so `"{3:'Fizz',5:'Buzz'}" however the program is still throwing an error for me.

What is the error?

@JasonS - Hi there. I'm interested in your experience of this challenge. http://meta.codegolf.stackexchange.com/questions/5050/thoughts-on-compiler-golf

perl6 376 340 84+115=199
UPDATE: switched from perl5 to perl6 to get say without use feature.
UPDATE: three test cases instead of five
There are hundreds of already-golfed solutions to FizzBuzz, and many contests end with the same result, so that's where I started. My compiler just produces a customized version of that solution. A few extra characters were inserted to account for the "just count" variation.
compiler, expects arguments like so: "Fizz 3" "Buzz 5"
print'say(('.(join'.',map{'('.(join')[$_%',split).']'}@ARGV).')||$_)for 1..$ARGV[0]'

compiled programs, expect argument like so: 100
say(()||$_)for 1..$ARGV[0]
say(((Golf)[$_%1])||$_)for 1..$ARGV[0]
say(((Fizz)[$_%3].(Buzz)[$_%5])||$_)for 1..$ARGV[0]

compiled programs for old test cases:
say(((Twoo)[$_%2].(Four)[$_%4].(Eiht)[$_%8])||$_)for 1..$ARGV[0]
say(((Twoo)[$_%2].(Thre)[$_%3].(Five)[$_%5].(Sevn)[$_%7])||$_)for 1..$ARGV[0]

I've changed the rules as discussed in the question's comments. You'll want to recalculate your score.

@billpg done, and improved :)

Hi there. I'm interested in your experience of this challenge. http://meta.codegolf.stackexchange.com/questions/5050/thoughts-on-compiler-golf

Pyth - 51 + (38 + 43 + 50) = 182 bytes
Can probably golf the compiler a few bytes. The links on all of them are permalinks to the online interpreter.
Compiler - 51 bytes
%"K[%s)=dc\"%s\"dFGr1hQJkFNKI!%%GN~J@dxKN))?JJG",zw

Just does string formatting with an input tuple. Takes input like:
3 5
Fizz Buzz

Nothing - 38 bytes
K[)=dc""dFGr1hQJkFNKI!%GN~J@dxKN))?JJG

Just Golf- 43 bytes
K[1)=dc"Golf"dFGr1hQJkFNKI!%GN~J@dxKN))?JJG

Classic Fizz Buzz - 50 bytes
K[3 5)=dc"Fizz Buzz"dFGr1hQJkFNKI!%GN~J@dxKN))?JJG

Common Lisp, 636 577
(ql:quickload'cl-ppcre)(lambda(z)(princ(subseq(ppcre:regex-replace-all" *([(')]) *"(with-output-to-string(@)(print`(lambda(n)(dotimes(i n)(loop for(m s)in ',z if(=(mod(1+ i)m)0)do(princ s))(do()((fresh-line))(princ (1+ i)))))@))"\\1")1)))

I took my other answer and wrapped it in quasiquotes while adding input parameters. I print the resulting form as a single-line and remove unnecessary whitespace characters.
The compiler is a little longer than the previous version, but the resulting score is reduced.
Score
(let ((*standard-output* (make-broadcast-stream)))
  (loop
     for form in '(215                      ; Compiler
                   ()                       ; Count
                   ((1 "Golf"))             ; Golf
                   ((3 "Fizz")(5 "Buzz")))  ; FizzBuzz
     for length = (if (numberp form) form
                      (length (funcall *fun* form)))
     collect length into lengths
     sum length into sum
     finally (return (values sum lengths))))

Returned values:
574
(215 111 119 129)

Pretty
(defun fizz-buzz-compiler (z)
  (princ (subseq
          (cl-ppcre:regex-replace-all
           " *([(')]) *"
           (with-output-to-string (stream)
             (print
              `(lambda (n)
                 (dotimes(i n)
                   (loop for (m s) in ',z
                      if (=(mod(1+ i)m)0)
                      do (princ s))
                   (do () ((fresh-line))
                     (princ (1+ i))))) stream))
             "\\1") 1)))

The input format is a list of (number string) couples. For example:
(fizz-buzz-compiler '((3 "Fizz")(5 "Buzz")))

... prints to standard output:
(LAMBDA(N)(DOTIMES(I N)(LOOP FOR(M S)IN'((3 "Fizz")(5 "Buzz"))IF(=(MOD(1+ I)M)0)DO(PRINC S))(DO NIL((FRESH-LINE))(PRINC(1+ I)))))

... which, pretty-printed, is:
(lambda (n)
  (dotimes (i n)
    (loop for (m s) in '((3 "Fizz") (5 "Buzz"))
          if (= (mod (1+ i) m) 0)
          do (princ s))
    (do () ((fresh-line)) (princ (1+ i)))))

Testing the resulting function:
CL-USER> ((lambda (n)
  (dotimes (i n)
    (loop for (m s) in '((3 "Fizz") (5 "Buzz"))
          if (= (mod (1+ i) m) 0)
          do (princ s))
    (do () ((fresh-line)) (princ (1+ i))))) 20)
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
17
Fizz
19
Buzz

Stax, 23+5+17+29=74
╥╟.└ç╘SJ∞CF╔v=▌╝Σ@∞ìé«g

Run and debug it
Shortest answer so far Not surprisingly beaten by Jelly. The string template provided in Stax is really neat and provides printf-like functions. The programs generated by the compiler are almost always as short as the best one can achieve by manually codegolfing, without using packing.
The compiler itself is 23  bytes long.
The ASCII equivalent is:
{H34|S_h"_`c%z`n?+"m"mz`cc_?

Provided input [], generates this one (5 bytes)
mzc_?

Run and debug it
Provided input [[1,"Golf"]], generates this one (17 bytes)
mz_1%z"Golf"?+c_?

Run and debug it
Provided input [[3,"Fizz"],[5,"Buzz"]], generates this one (29 bytes)
mz_3%z"Fizz"?+_5%z"Buzz"?+c_?

Run and debug it

Ruby 99 + (86 + 94 + 103) = 382
puts"(1..ARGV[0].to_i).each{|i|x=[];#{ARGV[0]}.each{|k,v|x<<v if i%k==0};puts x.size>0?x.join():i}"

Usage:
wc -c main.rb # 99 chars
ruby main.rb "{}" | ruby - 100 # 1..2..3..
ruby main.rb "{}" | wc -c # 86 chars
ruby main.rb "{1=>:Golf}" | ruby - 100 # Golf..Golf..Golf..
ruby main.rb "{1=>:Golf}" | wc -c # 94 chars
ruby main.rb "{3=>:Fizz,5=>:Buzz}" | ruby - 100 # 1..2..Fizz..4..Buzz..
ruby main.rb "{3=>:Fizz,5=>:Buzz}" | wc -c # 103 chars

C, 1080 bytes total
Compiler [369 bytes]
#include<stdlib.h>
r,t,f=3,b=5,n;char*F="FIzz",*B="buZZ";main(int c,char **v){if(f)for(c=atoi(v[1]),n=1;c>=n;)r=f?n%f:0,r?(t=b?n%b:0)?printf("%i\n",n):puts(B):r?printf("%s%s\n",F,B):puts(F),++n;else for(c=0;c<atoi(v[1]);)printf("%i\n",++c);}

Fizz Buzz [241]
#include<stdlib.h>
r,t,f=3,b=5,n;char*F="FIzz",*B="buZZ";main(int c,char **v){if(f)for(c=atoi(v[1]),n=1;c>=n;)r=f?n%f:0,r?(t=b?n%b:0)?printf("%i\n",n):puts(B):r?printf("%s%s\n",F,B):puts(F),++n;else for(c=0;c<atoi(v[1]);)printf("%i\n",++c);}

Golf [237]
#include<stdlib.h>
r,t,f=1,b=0,n;char*F="golf",*B="";main(int c,char **v){if(f)for(c=atoi(v[1]),n=1;c>=n;)r=f?n%f:0,r?(t=b?n%b:0)?printf("%i\n",n):puts(B):r?printf("%s%s\n",F,B):puts(F),++n;else for(c=0;c<atoi(v[1]);)printf("%i\n",++c);}

Count [233 bytes]
#include<stdlib.h>
r,t,f=0,b=1,n;char*F="",*B="";main(int c,char **v){if(f)for(c=atoi(v[1]),n=1;c>=n;)r=f?n%f:0,r?(t=b?n%b:0)?printf("%i\n",n):puts(B):r?printf("%s%s\n",F,B):puts(F),++n;else for(c=0;c<atoi(v[1]);)printf("%i\n",++c);}

Jelly, 88 84 83 73 bytes
Shortest answer so far (beats the previous "shortest answer" by 1 byte)
Compiler:
Ṿ€“ḍ@€“ẋ"Ð€F€ȯ"”jµFF?⁾RY

Try it online! (compiler)
Try it online! (verify the bytecount)

Statistics:

19 24 compiler
   20 golf
17  2 count
   27 fizzbuzz
83 73 total

Nice to see being beaten.

C++11 ~ 486 + (234 + 244 + 255) = 1219
First participation here, this challenge is not among the most difficult ones so I thought I'd give it a try.
Using C++ though, and even with C++11 additions it is still a pretty verbose language, but I'm sure there's room for improvement.
Compiler (486):
#include<sstream>
#include<iostream>
using namespace std;main(int c,char**v){stringstream t;int i;string s,o;o="#include <iostream>\n#include <map>\nusing namespace std;main(int c,char**v){int i,n=stoi(v[1]);map<int,string> f{";int z=2;for(int j=1;j<c;++j){t.str(v[j]);t.clear();t >> i; t >> s;o+="{"+to_string(i)+",\""+s+"\"}"+(z++==c?"":",");}o+= R"(};bool p;for(i=1;i<n;++i){p=true;for(auto e:f){if(i%e.first==0){cout<<e.second;p=false;}}cout<<(p?to_string(i):"")+"\n";}})";cout<<o;}

It assumes arguments in the form of 3Fizz 5Buzz etc.
Count (234):
#include <iostream>
#include <map>
using namespace std;main(int c,char**v){int i,n=stoi(v[1]);map<int,string> f{};bool p;for(i=1;i<n;++i){p=true;for(auto e:f){if(i%e.first==0){cout<<e.second;p=false;}}cout<<(p?to_string(i):"")+"\n";}}

Golf (244):
#include <iostream>
#include <map>
using namespace std;main(int c,char**v){int i,n=stoi(v[1]);map<int,string> f{{1,"Golf"}};bool p;for(i=1;i<n;++i){p=true;for(auto e:f){if(i%e.first==0){cout<<e.second;p=false;}}cout<<(p?to_string(i):"")+"\n";}}

FizzBuzz (255):
#include <iostream>
#include <map>
using namespace std;main(int c,char**v){int i,n=stoi(v[1]);map<int,string> f{{3,"Fizz"},{5,"Buzz"}};bool p;for(i=1;i<n;++i){p=true;for(auto e:f){if(i%e.first==0){cout<<e.second;p=false;}}cout<<(p?to_string(i):"")+"\n";}}

Additional information
Tested with GCC 4.8.1, no compiler cheats.
Here is a small makefile to automate the generation of the test cases and run them (use make run):
run:
    g++ main.cpp --std=c++11 -o fbc

    ./fbc > count.cpp
    g++ count.cpp --std=c++11
    echo "======= Count ========"
    ./a.out 15

    ./fbc 1Golf > golf.cpp
    g++ golf.cpp --std=c++11
    echo "======= Golf ========"
    ./a.out 15

    ./fbc 3Fizz 5Buzz > fizzbuzz.cpp
    g++ fizzbuzz.cpp --std=c++11
    echo "======= FizzBuzz ========"
    ./a.out 15

Hi there. I'm interested in your experience of this challenge. http://meta.codegolf.stackexchange.com/questions/5050/thoughts-on-compiler-golf

map<int,string> f could be map<int,string>f. You could initialize j=1 at the same time with z.

Perl 5, 77 + 93, 170 bytes
say"say",(map{++$i%2?"'$_":"'x!(\$_%$_)".($i<$#F?'.':'||$_')}@F),' for 1..<>'

Try the compiler online!
Try just count online!
Try just golf online!
Try fizz buzz online!

vim, 122 (compiler) + 73 (empty) + 90 (golf) + 123 (fizzbuzz) = 392 bytes
Compiler
:%s/\v(.*):(.*)/qq\1jA\2<C-V><C-V><C-V><ESC>q=@qgg
VgggJAddGdd:%s/\v[0-9]*([^0-9])/\1
<C-V><ESC>:%@n
:w
:so! %
<ESC>ggii%s/=/<C-V><ESC><C-V><C-A>a/g<C-V><ESC>"ncc:%!seq 0 =
<ESC>

Input format
3:Fizz
5:Buzz

Generated code for FizzBuzz case
i%s/=/<ESC><C-A>a/g<ESC>"ncc:%!seq 0 =
qq3jAFizz<C-V><ESC>q=@qggqq5jABuzz<C-V><ESC>q=@qggddGdd:%s/\v[0-9]*([^0-9])/\1
<ESC>:%@n
:w
:so! %

Generated Code, Annotated
# replace the input number with a regex that replaces the placeholder (=)
# with the real number + 1 (we'll need an extra line as a terminator later)
i%s/=/<ESC><C-A>a/g<ESC>

# pull the substitution command into register c and enter insert mode
"ncc

# create the numbers 0..N+1
:%!seq 0 =

# for each word, scan down k lines at a time and append the word to each
qq3jAFizz<C-V><ESC>q=@qgg
qq5jABuzz<C-V><ESC>q=@qgg

# delete the 0 and N+1 lines
ddGdd

# remove the numbers from any line with words
:%s/\v[0-9]*([^0-9])/\1
<ESC>

# Run the command we created at the beginning, replacing the placeholder
# with the real number
:%@n

# The file now contains yet another program, with the constants defined.
# Save and run.
:w
:so! %

# The file now contains a program that, when run on a buffer containing
# a single line with a number, will produce the appropriate output

<C-V> is 0x16. <ESC> is 0x1b. <C-A> is 0x01.
Example session
$ cat code.txt
2:Foo
4:Bar
$ cat input.txt
8
$ { cat compile.vim; echo ':wq'; } | vim code.txt
# code.txt now contains the generated code
$ { cat code.txt; echo ':wq'; } | vim input.txt
$ cat input.txt
1
Foo
3
FooBar
5
Foo
7
FooBar

There's something odd happening when I try to define and run a macro from within another macro.  If I manage to sort that out, I might save a few bytes over the save and source approach.

dc, 434 bytes
[:a]sa[91Pn93Pznlanps_znlanz0<R]sR[[[lj1-;aP1sb]sB0sj[dljd2+sj;a%0=Bljlz>F]sF[p2Q]sP]P]sI[[[]sF[pq]sP]nq]sN[z0=Nzn[sz]PlRxlIx]x[sn0dsb[1+0sjlFx[lb0=PAP]x0sbdln>M]dsMx]P

Try it online!
Input for the compiler (168 bytes) should be placed on the stack as integer, string, integer, string, and so on (3 [Fizz] 5 [Buzz]). It should be given in the order one wants their fizzes and buzzes to be printed, which may be a bit of a cheat (having implemented bubble sort in dc before, I believe it would cost me around 100 bytes) but it also allows the user to, say, still have 'Fizz' run on 3 and 'Buzz' run on 5, but have 15 yield 'BuzzFizz'.
I'm sure this can be golfed a bit more; the main macro in the final program (M) relies on two macros (F and P) that are rather unnecessary given no input. Right now the compiler checks for input and outputs different (much smaller) versions of these macros if there is none, but I'm not sure the whole setup is optimal.
The compiler itself is pretty straightforward, it just checks to see if there are 'rules' on the stack, and if so it prints code that stores the stack depth in z, stores the stack in a 0-indexed array a, and then prints the generalized FizzBuzz code. If there was nothing on the stack, it really just prints a modified version of the FizzBuzz code. Test cases:
No input (46 bytes):
[]sF[pq]sPsn0dsb[1+0sjlFx[lb0=PAP]x0sbdln>M]dsMx

3[Fizz]5[Buzz] (117 bytes):
4sz[Buzz]3:a5
2:a[Fizz]1:a3
0:a[lj1-;aP1sb]sB0sj[dljd2+sj;a%0=Bljlz>F]sF[p2Q]sPsn0dsb[1+0sjlFx[lb0=PAP]x0sbdln>M]dsMx

1[Golf] (103 bytes):
2sz[Golf]1:a1
0:a[lj1-;aP1sb]sB0sj[dljd2+sj;a%0=Bljlz>F]sF[p2Q]sPsn0dsb[1+0sjlFx[lb0=PAP]x0sbdln>M]dsMx

They all expect the n value on the stack, this gets stored in n. The ones that have 'rules' place them in the array a, with the strings at odd indices and the integers at evens. The main macro, M, increments whatever is on the stack, runs macro F which checks the value against array a, checks whether F set register b to truthy or not and prints the top of stack if so or a newline if not, resets b to falsy, and then keeps running itself if n hasn't been reached yet. Macro F, given rules, goes through the whole array looking for matches. It increments by two since our integers and strings are woven through the array, and on a match it calls macro B. Macro B just retrieves the string (current position in array less one), and prints it. It also sets b to truthy. Our compiler doesn't bother to print B for no input, and essentially makes F a nop.

SlooSarksi .Lang, 179
%%--43^jjk"/][][0[#!#111# h SD G ergDFGdfg[]9--99+==

I'm not familiar with this language; could you link us to a page describing it?


text:
Don't. Even. Blink

Your life could depend on this. Don't blink. Don't even blink. Blink and you're dead. They are fast. Faster than you can believe. Don't turn your back, don't look away, and don't blink! Good luck.

Weeping Angels are an alien race that cannot move while being observed by another being (even another Angel). They feed by sending their victims back in time. You (The Doctor) are trapped in a room with some, and you need to get to your TARDIS.

Task
Write a program that will, given an ASCII representation of a rectangular room, output a path that will lead you to safety. If any Angel can attack — at any time during your progress — then that path is not safe. An Angel can attack if it can see you while not being seen by you or another Angel.
Input
Input is two parts. First, the direction you're facing (NSEW). Then on succeeding lines, a representation of the room, showing start/end locations, and the location/facing of all Angels.
The sample below shows that there is one angel facing west, and you start facing south.
S
..........
....D.....
..........
..........
..........
..........
..........
..........
.........W
..........
...T......

. - Empty space
D - The Doctor (starting position)
T - The TARDIS (end position)
N,S,E,W - An Angel, facing the direction specified (north, south, east, west)

Line of sight
You can see any space withing 45 degrees of the direction you're facing. Line of sight is obstructed if there is another entity along a direct horizontal, vertical, or 45-degree diagonal. Any other diagonal does not obstruct the view. Angels' line of sight works in the same way. For example, in the following, - represents your field of view, assuming you're facing south.
........
...D....
..---...
.-----..
-------.
---N----
---.--N-
---.----

Output
The output is a string representing the path you will take to exit. If there are multiple safe paths, choose any one. If no path is safe, output 0. If the map is malformed, do whatever you like, including crashing out. Consider it malformed if the room is not rectangular, there is no exit, etc. If there are no Angels, it's not malformed, simply easy.
For each step, you can do one of two things: move in a NSEW direction, or turn to a NSEW direction (without changing positions). To move, simply output the letter for that direction. To turn to face a direction, output F followed by the appropriate letter. For example, the following output:
SSFESSSSSSSW

is a safe path for the sample given in the input section. You move south twice, face east to keep the angel in sight, then move south seven more times and west once to enter the TARDIS.
Test Cases
1) You can go around the east-facing Angel to get to the TARDIS. Unless you step directly between them, they lock each other in place, so it doesn't matter which way you're facing at any point.
W
...D....
........
........
........
.E.....W
........
........
...T....

2) You lose. There's no way to get past them. They can see each other until you step between them. At that point, you can't face them both and you're done. Might as well just shut your eyes and get it over with.
S
...D....
........
........
........
E......W
........
........
...T....

Winning
Standard golf rules and loopholes apply, least bytes wins. I'll try to get some more test cases soon, but feel free to suggest your own in the meantime.
Image and quote from Doctor Who.

can we use a library for finding a path through a graph?

@Sparr Yes, but anything necessary to load/include the library should be added to the byte count.

any constraints on room size?

@Sparr In the interests of limiting it to a finite amount of memory/space/time, let's say the largest test case will be 50x50. A valid program should theoretically be able to handle any room size, given infinite resources.

roger that. I had some golf-y ideas if 10x10 was the largest.

Obviously use a vortex manipulator!

@TheDoctor Jack took his with him, and you can see he isn't on any of the maps (J).

Can the input (direction and room) be read from a file or does it have to be passed as a command line argument?

@Timmy Any of the standard definitions can be used.

Doesn't the lower right corner in the Line of Sight example has to be a . instead of a -, as there is an angel obstructing it?

@Padarom No, because the Angel is not on a 45- or 90-degree angle from The Doctor.

This reminds me a lot of the game Nothing to Hide, which has its game level definitions written in ascii. (Open source on Github: https://github.com/ncase/nothing-to-hide )

Python – 559 565 644 633
M=input()
I=1j
Q={"S":I,"N":-I,"E":1,"W":-1}
A=[]
e=enumerate
for y,l in e(M[2:].split()):
 for x,c in e(l):
    P=x+y*1j
    if c=="D":D=(P,Q[M[0]])
    elif c=="T":T=P
    elif c!=".":A+=[(P,Q[c])]
def s(D,h,r=[]):
 def L(X,p,d):
    S=[p+d*(i+j*I)for i in range(x+y)for j in range(-i+1,i)if j]
    for f in[1,1+I,1-I]:
     i=0
     while i<x+y>1>(S[-1]in[a[0]for a in[D]+A]+[T])*i:i+=1;S+=[p+i*f*d]
    return X[0]in S
 if y>=D[0].imag>=(D[0]in[a[0]for a in A])<all(any(L(a,*b)for b in[D]+A)for a in A if L(D,*a))>(D in r)<=D[0].real<=x:
    r+=[D]
    if D[0]==T:print h;exit()
    for n in"SWEN":s((D[0]+Q[n],D[1]),h+n,r);s((D[0],Q[n]),h+"F"+n,r)
s(D,"")
print"0"

Input has to be provided like this:
"W\n...D....\n........\n........\n........\nE......W\n........\n........\n...T....\n"

Essentially it’s this approach applied to finding all states (position and direction) the Doctor can safely reach, storing how he got there and printing the way in case of success. Positions and directions are realised with complex numbers.
I could probably safe some chars using Sage’s complex number arithmetics, but that would run extremely long.
I first thought I could save six characters by having the Doctor turn into a specific direction after reaching the Tardis, but I realised that this could result in wrong solutions.
Also I first misread the rules.
Here is a mostly ungolfed version:
Map = input()

I = 1j
string_to_dir = {"S":I,"N":-I,"E":1,"W":-1}

Angels = []
Pos = 0
direction = string_to_dir[Map[0]]
for y,line in enumerate(Map[2:].split()):
    for x,char in enumerate(line):
        Pos = x+y*1j
        if char == "D":
            Doctor = (Pos, direction)
        elif char == "T":
            Tardis = (Pos, direction)
        elif char != ".":
            Angels += [(Pos,string_to_dir[char])]

reachables = []

def display(LoS, Doctor):
    string = ""
    for y,line in enumerate(Map[2:].split()):
        for x,char in enumerate(line):
            if x+y*1j == Doctor[0]:
                string += "D"
            elif x+y*1j in LoS:
                if char in ".D":
                    string += "*"
                else:
                    string += "X"
            elif char != "D":
                string += char
            else:
                string += "."

        string += "\n"
    print string

def LoS(angel,Doctor):
    p,d = angel
    Sight = []
    for i in range(x+y):
        for j in set(range(-i+1,i))-{0}:
            Sight += [p+d*i+d*j*I]
    for line in [d, (1+I)*d, (1-I)*d]:
        for i in range(1,x+y):
            Pos = p + i*line
            Sight += [Pos]
            if Pos in [angel[0] for angel in Angels+[Doctor, Tardis]]:
                break
    return Sight

def search(Doctor, history):
    global reachables

    Sight = sum([LoS(angel, Doctor) for angel in [Doctor]+Angels],[])

    if (
                all(angel[0] in Sight for angel in Angels if Doctor[0] in LoS(angel, Doctor))
            and not (Doctor in reachables)
            and (0<=Doctor[0].imag<=y)
            and (0<=Doctor[0].real<=x)
            and (Doctor[0] not in [angel[0] for angel in Angels])
        ):

        reachables += [Doctor]

        if Doctor[0] == Tardis[0]:
            print history
            exit()
        for new_direction in "SWEN":
            search((Doctor[0]+string_to_dir[new_direction], Doctor[1]), history + new_direction)
            search((Doctor[0], string_to_dir[new_direction]), history + "F" + new_direction)

search(Doctor, "")
print "0"

Test Cases
Test case 1:
SSSFSWWWSSSSFWEFSEFWE

Test case 2:
0

VisualMelon’s test case:
SSFWSSSSSFSWWSSWWWFWEEEEFSEFWEFSE

I've not tested your code, but it appears that you've pasted the output for test case 1 twice! Also I'd be interested to see what your program produces if you feed it my proposed test case.

@VisualMelon: Thank you for spotting and I integrated the test case.

C# 1771 2034 1962 1887 1347bytes
Re-wrote the blocking LOS checking in 1 loop, making it much tidier, and about 450bytes shorter
using C=System.Console;using T=System.Math;struct P{int x,y,d;static void Main(){int v=C.ReadLine()[0],w,h,i,o=0,x=0,y=0,O,E,F,e=46;var R=C.In.ReadToEnd().Replace("\r","");var M=new int[w=R.IndexOf("\n"),h=(R.Length+1)/(w+1)];for(;o<h;o++)for(i=0;i<w;i++)if((M[i,o]=R[o+o*w+i])==68)M[x=i,y=o]=e;System.Func<int,int,int,bool>S=null;S=(X,Y,D)=>{var Z="SSSE_WNNNE_W___E_W";int I=0,H=0,L=0,J=Y,K=M[X,Y],B;M[X,Y]=D>0?D:K;for(H=0;H<9;H++)for(I=X,J=Y;H!=4&(I+=H%3-1)<w&I>=0&(J+=H/3-1)<h&&J>=0;){if(((B=M[I,J])==Z[H]|B==Z[H+9])&(D<1||!S(I,J,0)))goto W;if(B!=e)break;}for(B=I=-1;++I<w;B=1)for(J=0;J<h;J++)if(I!=X&J!=Y&(((B=M[I,J])==87&I>X&(H=T.Abs(J-Y))<I-X)|(B==69&I<X&H<X-I)|(B==78&J>Y&(L=T.Abs(I-X))<J-Y)|(B==83&J<Y&L<Y-J))&(D<1||!S(I,J,0)))goto W;W:M[X,Y]=K;return B>1;};P a,p=new P{x=x,y=y,d=v};var A=new System.Collections.Generic.List<P>();System.Action q=()=>{if(((E=M[p.x,p.y])==e|E==84)&!A.Contains(p)&!S(p.x,p.y,p.d))A.Add(p);};q();for(o=0;(O=A.Count)!=o;o=O)for(i=O;i-->o;){p=A[i];if((E=M[p.x,p.y])==84)for(R="";;p=a){i=0;n:a=A[i++];O=T.Abs(p.y-a.y)+T.Abs(a.x-p.x);if(O==1&p.d==a.d)R=(a.y-p.y==1?"N":p.y-a.y==1?"S":a.x-p.x==1?"W":"E")+R;else if(O<1)R="F"+(char)p.d+R;else goto n;if(i<2)goto Z;}if(E==e){if(p.x-->0)q();p.x+=2;if(p.x<w)q();p.x--;if(p.y-->0)q();p.y+=2;if(p.y<h)q();p.y--;for(F=0;F<4;q())p.d="NESW"[F++];}}R="0";Z:C.WriteLine(R);}}

This is a complete program that expects the input to terminate with an EOF and be passed to STDIN. It (hopefully) prints the shortest path to the TARDIS, or "0" if no path exists. It uses a shoddy Breadth First Search to follow all possible routes, then it backtracks from the TARDIS to The Doctor to assemble the output.
Formatted code:
using C=System.Console;
using T=System.Math;

struct P
{
    int x,y,d;

    static void Main()
    {
        int v=C.ReadLine()[0],w,h,i,o=0,x=0,y=0,O,E,F,e=46;
        var R=C.In.ReadToEnd().Replace("\r","");
        var M=new int[w=R.IndexOf("\n"),h=(R.Length+1)/(w+1)];

        for(;o<h;o++)
            for(i=0;i<w;i++)
                if((M[i,o]=R[o+o*w+i])==68)
                    M[x=i,y=o]=e;

        System.Func<int,int,int,bool>S=null;
        S=(X,Y,D)=>
        {
            var Z="SSSE_WNNNE_W___E_W";

            int I=0,H=0,L=0,J=Y,K=M[X,Y],B;
            M[X,Y]=D>0?D:K;

            for(H=0;H<9;H++)
                for(I=X,J=Y;H!=4&(I+=H%3-1)<w&I>=0&(J+=H/3-1)<h&&J>=0;)
                {
                    if(((B=M[I,J])==Z[H]|B==Z[H+9])&(D<1||!S(I,J,0)))
                        goto W;
                    if(B!=e)
                        break;
                }

            for(B=I=-1;++I<w;B=1)
                for(J=0;J<h;J++)
                    if(I!=X&J!=Y&(((B=M[I,J])==87&I>X&(H=T.Abs(J-Y))<I-X)|(B==69&I<X&H<X-I)|(B==78&J>Y&(L=T.Abs(I-X))<J-Y)|(B==83&J<Y&L<Y-J))&(D<1||!S(I,J,0)))
                        goto W;
        W:
            M[X,Y]=K;
            return B>1;
        };

        P a,p=new P{x=x,y=y,d=v};
        var A=new System.Collections.Generic.List<P>();
        System.Action q=()=>{if(((E=M[p.x,p.y])==e|E==84)&!A.Contains(p)&!S(p.x,p.y,p.d))A.Add(p);};
        q();

        for(o=0;(O=A.Count)!=o;o=O)
            for(i=O;i-->o;)
            {
                p=A[i];
                if((E=M[p.x,p.y])==84)
                    for(R="";;p=a)
                    {
                        i=0;
                    n:
                        a=A[i++];

                        O=T.Abs(p.y-a.y)+T.Abs(a.x-p.x);
                        if(O==1&p.d==a.d)
                            R=(a.y-p.y==1?"N":p.y-a.y==1?"S":a.x-p.x==1?"W":"E")+R;
                        else if(O<1)
                            R="F"+(char)p.d+R;
                        else goto n;

                        if(i<2)
                            goto Z;
                    }
                if(E==e)
                {
                    if(p.x-->0)q();
                    p.x+=2;if(p.x<w)q();p.x--;
                    if(p.y-->0)q();
                    p.y+=2;if(p.y<h)q();p.y--;

                    for(F=0;F<4;q())
                        p.d="NESW"[F++];
                }
            }
        R="0";
    Z:
        C.WriteLine(R);
    }
}

Output for example input
SFESWSSSSSSS

Output for test case 1)
WSWSWSSSESESE

Output for test case 2)
0

I present, as requested, a new test case:
S
..E..DS....
...........
...........
...........
...........
...........
...........
...........
....SSSSS.W
.......T...

My program outputs
SESESESESFNSSSSWW

WozzeC's Test Case 1:
EEEEFWSSSFNWWN

WozzeC's Test Case 2:
FSEEEESFWSSSSWFNWWWNFENNEES

I have totally missed the using X=System.Console possibility. Thank you for that :)

@WozzeC you might want to check out Tips for code-golfing in C#

I believe the doctor is attacked at startup with your test case :S

@WozzeC The West angel in the South-East can see the East angel in the North-West, so The Doctor can escape, but on that point, it appears my solution does not notice if the doctor is attacked at startup. Why is this code so hard to test!

A sorry, never mind. I missed the small detail that they cannot move if another angel is watching.

You could gain ONE byte using class instead of struct.. :P

@TopinFrassi I rely on P being compare by value, which is why I chose struct rather than class, so I'm afraid I can't make any gains there! (You may notice that I only ever create one instance of P, I then just modify copies of it to produce 'more' as I go along as they are all derivatives of each other)

From what I can see @VisualMelon has a correct test case. Anything failing that is wrong. South & West facing angels are always watched. The only angel that can get you is E if you get between that and the westfacing angel thus blocking the W from seeing it. Facing north stops that.

Awh nuts... where am I going to drop 30 chars...

@WozzeC for starters you can replace "No way out" with "0", as I did when the competition arrived - desperate times call for actually following the spec ;)

C# 1454,  1396, 1373, 1303 1279
class P{static int x,d,y=x=d=55,o=170,X=0,Y=0,u,k=3;static string[,]t=new string[o,o];static int[,]m=new int[o,o];static string e=" NS ETD W      .",q="0";static void Main(string[]s){m[0,1]=m[1,8]=-1;m[0,2]=m[1,4]=1;u=e.IndexOf(s[0][0]);for(;k<s[0].Length;k++){var c=s[0][k];if(c=='D'){X=x;Y=y;}if(c=='\\'){y++;x=d;k++;}else m[y,x++]=e.IndexOf(c);}k=A(X,Y,1);if((k&u)!=0){W(X,Y,k,"");}System.Console.Write(q);}static void W(int x,int y,int h,string s){t[y,x]=s;for(int i=1;i<9;i*=2){int l=y+m[0,i],g=x+m[1,i];if(m[l,g]==5)q=t[l,g]=s+e[i];else if(m[l,g]==15){m[l,g]=6;m[y,x]=15;int n=A(g,l,1),U;for(int j=1;j<9;j*=2){var z=t[l,g]??s;if((n&h&j)!=0&z.Length>=s.Length){U=u;u=j;W(g,l,n,s+((u!=j)?"F"+e[j]:"")+e[i]);u=U;}}m[y,x]=6;m[l,g]=0;}}}static int A(int x,int y,int L){int r=15,a,b,c,f=0,g,h,R,B;for(a=1;a<d-5;a++){g=1;for(b=y-a;b<=y+a;b++)for(c=x-a;c<=x+a;c++){B=m[b,c];R=0;bool W=(c+a-x)%a==0,V=(b+a-y)%a==0,z=W&V;if(B>0&B<9&B!=6&B!=5&g!=16&!((W|V)&(f&g)!=0)){h=R;if(b==y-a){R=1;if(c==x-a){h=4;R=9;}else if(c==x+a){h=8;R=5;}B&=h&2;}else if(b==y+a){R=2;if(c==x-a){h=4;R=10;}else if(c==x+a){h=8;R=6;}B&=h&1;}else if(c==x-a){B&=4;R=8;}else if(c==x+a){B&=8;R=4;}else B=0;if(B!=0){if(L==1&&A(c,b,0)==15)r&=R;if(L==0)return R;}}if(z){if(B<9&B>0&!(c==x&y==b))f|=g;g*=2;}}}return r;}}

Right. So I decided to give this a go, and boy did it take a while. It's built up mostly using logical operators.

North = 1 = N
South = 2 = S
East = 4 = E
West = 8 = W
Doctor = 6 = D
TARDIS = 5 = T
15 = . <-All free spaces

To avoid having to check for Null etc. I decided to use a field of [MAX_SIZE*3]*[MAX_SIZE]*3 and put the game board close to the center.
Loop checks are done inside and out all the way to 50(MAX_SIZE). So something like this:
22222
21112
21D12
21112
22222

When a E W S or N is found I do the same check on their part. If anything is found looking at the Angels (Not the Doctor) they return 15 as free passage. If they are not looked upon they return in which way the Doctor should face to be safe. i.e N would return 2 for south. Unless it is NW or NE in which case it would return 6(2+4) and 10(2+8) respectively.
If two angels are watching the Doctor the return values from these would be "ANDed" so in the test example 2 crunchpositions 4 AND 8 would turn into 0. Meaning that the position is bad and should be avoided.
Expanded code:
class P
{
    static int x,d,y=x=d=55,o=170,X=0,Y=0,u,k=3;
    static string[,] t = new string[o, o];
    static int[,] m = new int[o, o];
    static string e = " NS ETD W      .", q="0";
    static void Main(string[]s)
    {
        m[0, 1]=m[1, 8]=-1;
        m[0, 2]=m[1, 4]=1;
        u=e.IndexOf(s[0][0]);
        for (;k<s[0].Length;k++)
        {
            var c = s[0][k];
            if (c == 'D') { X = x; Y = y; }
            if (c == '\\') { y++; x = d; k++; }
            else m[y, x++] = e.IndexOf(c);
        }
        k=A(X,Y,1);
        if ((k&u)!=0)
        {
            W(X, Y, k,"");
        }
        System.Console.Write(q);
    }
    static void W(int x,int y,int h,string s){
        t[y, x] = s;
        for (int i = 1; i < 9; i*=2)
        {
            int l = y+m[0, i], g = x+m[1, i];
            if (m[l, g] == 5)
                q = t[l, g] = s + e[i];
            else if (m[l, g] == 15)
            {
                m[l, g] = 6;
                m[y, x] = 15;
                int n = A(g, l,1),U;
                for (int j = 1; j < 9; j *= 2)
                {
                    var z = t[l, g]??s;
                    if ((n & h & j) != 0 & z.Length>=s.Length)
                    {
                        U = u;
                        u = j;
                        W(g, l, n,s+((u != j) ? "F" + e[j] : "") + e[i]);
                        u = U;
                    }
                }
                m[y, x] = 6;
                m[l, g] = 0;
            }
        }
    }
    static int A(int x, int y,int L)
    {
        int r = 15,a,b,c,f=0,g,h,R,B;
        for (a = 1; a < d - 5; a++)
        {
            g = 1;
            for (b = y - a; b <= y + a; b++)
                for (c = x - a; c <= x + a; c++)
                {
                    B=m[b, c];
                    R=0;
                    bool W=(c+a-x)%a==0,V=(b+a-y)%a==0,z=W&V;
                    if (B>0&B<9&B!=6&B!=5&g!=16&!((W|V)&(f&g)!=0))
                    {
                        h=R;
                        if (b==y-a)
                        {
                            R=1;
                            if(c==x-a){h=4;R=9;}
                            else if(c==x+a){h=8;R=5;}
                            B&=h&2;
                        }
                        else if (b==y+a)
                        {
                            R=2;
                            if(c==x-a){h=4;R=10;}
                            else if (c==x+a){h=8;R=6;}
                            B&=h&1;
                        }
                        else if(c==x-a){B&=4;R=8;}
                        else if(c==x+a){B&=8;R=4;}
                        else B=0;
                        if (B!=0)
                        {
                            if(L==1&&A(c,b,0)==15)r&=R;
                            if (L==0)return R;
                        }
                    }
                    if (z)
                    {
                        if (B < 9 & B > 0 & !(c==x&y==b))
                           f |= g;
                        g *= 2;
                    }
                }
        }
        return r;
    }
}

Test results
1 Example: FNSSSWNNNWSSSWSSSSENNESES
2 Example: No way out
VisualMelon Example: FNSSSSSSSWNNNNNNNWSSSSSSSSSEEEE
My Test case1: FSSENEEEFWSSFNSWWN
My Test case2: FSEEEESFWSSSSFNWWWWNFENNFSEES
As can be seen my Doctor loves strutting around like a douche to show the Angels how fun it is to move around. I can make the software find the shortest path, but it takes longer and needs more code.
Test cases for you guys
S
D....
..NE.
.WTS.
.S...

Another one:
E
D....
WNNN.
...E.
.WTE.
.SSE.
.....

The golfed code is missing a space at one place that stops it compiling, but with that fix I make you byte count only 1395! Nice work getting it so low, and it's perfectly fair game for you to use using S=System.Console;, or you could simply remove the S altogether in your code and save 6 bytes by using System. Now I'll have to try and trim my naive approach down some more... ;)

Oh a missed space, I should take care of that. And of course the S=... Got a bit carried away when I learned that. :)

Nice work getting the byte count down ;)

I found some code that were never used. Plus some additional unneccessary stuff.