# Prime Time Travel

Don't tell anyone, but I've nicked my uncle's time travel machine! My uncle is obsessed with prime numbers, though, and that shows in the machine — he has programmed it so that it can only go to dates that sum up to a prime number.

So it can't go to 1947-08-15 because 1947+8+15 = 1970, which is not a prime number. It can go to 1947-07-25, because 1947+7+25 = 1979, which is prime. So if I want to go back to watch India's independence celebrations, it looks like I'll have to go a few weeks earlier and wait out those 20 days.

I have some other dates that I want to go to, and I'll similarly have to go to a date before (or if I'm lucky, equal to) my target date, that sums up to a prime number. I'm impatient, though, and don't want to wait too much — so I want to find the date I can use that is closest to my target date.

Can you write me a program that takes my target date and gives me the date I should input into the time machine — the closest date before or equal to the given date whose parts add up to a prime number?

(For this challenge, we're using the proleptic Gregorian calendar — which simply means we use the current Gregorian calendar even for periods when people then were using the older Julian calendar.)

### Input

• A date
• ideally, any date in the Current Era (AD); practically, whatever subset of that your language can naturally handle
• in any single human-readable format⁺ you like

### Output

• The date closest to the input date, which is less than or equal to the input and whose date+month+year sums up to a prime number.
• in any single human-readable format⁺ you like

⁺: "human readable" as in the day, month and year all separately spelt out, in whatever order

### Test cases

1947-08-15
=> 1947-07-25
1957-10-04
=> 1957-09-27
1776-07-04
=> 1776-07-04
999-12-12
=> 0999-12-10
2018-06-20
=> 2018-06-15
1999-01-02
=> 1998-12-29
1319-12-29
=> 1319-07-01


(Thanks to @Shaggy, @PeterTaylor, and @Arnauld for help with the question.)

• Is it OK to have a nonsense time in the output? (e.g. Fri Jul 25 02:46:39 CEST 1947) – wastl Jun 20 '18 at 14:09
• @wastl Yes, as long as the date info is a contiguous fixed length substring of the output (so no for that particular example). – sundar Jun 20 '18 at 15:25

# Red, 87 bytes

func[d][d: d + 1 until[d: d - 1 n: d/2 + d/3 + d/4 i: 1 until[n %(i: i + 1)= 0]i = n]d]


Try it online!

f: func [ d ] [
d: d + 1
until [
d: d - 1
n: d/day + d/month + d/year
i: 1
until [
i: i + 1
n % i = 0
]
i = n
]
d
]


# JavaScript (Node.js), 94 bytes

Takes input as 3 integers in currying syntax (year)(month)(day). Returns a hyphen-separated string with a leading hyphen.

y=>m=>g=d=>(P=k=>n%++k?P(k):~k)(n=eval(s='-'+new Date(y,m-1,d).toJSON().splitT[0]))?g(d-1):s


Try it online!

### How?

We first convert the date to JSON format yyyy-mm-ddT00:00:00.000Z (ISO 8601), split it on the 'T', keep only the left part and add a leading hyphen, which gives -yyyy-mm-dd.

s = '-' + new Date(y, m - 1, d).toJSON().splitT[0]


This expression s can now be eval()'uated to get the opposite n of the sum of year + month + day.

n = eval(s)


We use the helper function P() to test whether -n is prime (in which case it returns 0). If it is, we return s. Otherwise, we try again with the previous day.

(P = k => n % ++k ? P(k) : ~k)(n) ? g(d - 1) : s

• I feel like I need a day off just from understanding how that prime check works and terminates. Good golfing! – sundar Jun 20 '18 at 13:05

# Python 2, 130 127 bytes

Input is year, month, day.

-3 bytes thanks to Kevin Cruijssen.

from datetime import*
def f(a):
while(lambda n:any(n%m<1for m in range(2,n)))(a.year+a.month+a.day):a-=timedelta(1)
print a


Try it online!

• You are allowed to take a date-object as input, so you can save 3 bytes. – Kevin Cruijssen Jun 20 '18 at 12:42
• @KevinCruijssen thank you. Do you think this is a valid input format? – ovs Jun 20 '18 at 13:50
• I don't see why it wouldn't be, so that's another -4. Hadn't thought about that. – Kevin Cruijssen Jun 20 '18 at 14:08

# Java 8, 144 128 bytes

d->{for(;;d=d.minusDays(1)){int n=d.getYear()+d.getMonthValue()+d.getDayOfMonth(),i=2;for(;i<n;n=n%i++<1?0:n);if(n>1)return d;}}


Try it online.

java.time.LocalDate class has been an improvement in comparison to the old java.util.Date, but why did they had to make those names longer (getMonthValue and getDayOfMonth instead of getMonth and getDay).. >.>

Explanation:

d->{                      //  Method with LocalDate as both parameter and return-type
for(;;                  //  Loop indefinitely
d=d.minusDays(1)){  //    Going one day back after every iteration
int n=d.getYear()+d.getMonthValue()+d.getDayOfMonth(),
//   Set n to the sum of year+month+day
i=2;for(;i<n;n=n%i++<1?0:n);if(n>1)
//   If n is a prime:
return d;}}         //    Return the now modified input-LocalDate d


# Ruby, 94 bytes

Try it online!

Takes a single Date input, and returns a string in the ISO 8601 format (YYYY-MM-DD).

require'date'
require'prime'
->d{d.downto(0){|i|break i.to_s if (i.day+i.month+i.year).prime?}}


It uses Ruby's prime module. If that's not allowed, or frowned upon, then for two bytes more I present this abomination:

# Ruby, 97 bytes

Try it online!

It uses a check for a number being prime from this stackoverflow answer. I have no idea how this works, it looks a bit like witchcraft. Same input as above, and same output.

require'date'
->d{d.downto(0){|i|break i.to_s if ?1*(i.day+i.month+i.year)!~ /^1?$|^(11+?)\1+$/}}

• Using modules is perfectly fine as long as the import lines are included in the byte count (which you've done here). It seems like you don't need the parantheses around the initial d and the space after the if though, so you can shave off 3 bytes from your first answer removing those. TIO link – sundar Jun 20 '18 at 12:19
• I do like the witchcrafty abomination though. It's pretty neat and simple once you look into it: ?x*n !~ /^x?$|^(xx+?)\1+$/ = to check if n is prime, make a string of n 'x's, check that it's not 0 or 1 x's (which are not prime), and that it doesn't match any 2 or more x's repeating itself (matching ^(xxxxx)\1+$ would mean n is divisible by 5). It abuses the regex engine's backtracking to do our looping for us - it's brilliant, it's monstrous, and animal sacrifice was probably involved in its discovery. – sundar Jun 20 '18 at 12:42 • Good spot about the parentheses and the space! Thanks. – IMP1 Jun 20 '18 at 13:22 • The "witchcraft" version can be done in 92 bytes, see here. Because the sum we want to check for primality is at least 3 (since minimum date 0001-01-01 sums to 1+1+1=3), we can remove the part of the regex that is specifically to handle input being 0 or 1. Removing that and simplifying gives a 91 byte version. – sundar Jun 20 '18 at 19:02 • An interesting approach. Save 2 bytes by using 'mon' instead of 'month' – G B Jun 21 '18 at 6:54 # Ruby, 57 53 bytes ->d{d-=9until/^(11+)\1+$/!~?1*(d.day+d.year+d.mon);d}


Try it online!

Not my idea - stolen from the "abomination" by IMP1

# Ruby, 59 bytes

->d{d-=9until((2...w=d.day+d.year+d.mon).all?{|x|w%x>0});d}


Try it online!

• Would using 8e4 instead work? – Cows quack Jun 21 '18 at 12:19
• Yes, of course it works. It also works using 9 or any other smaller number. It only takes a lot longer to run. Thanks. – G B Jun 21 '18 at 12:24

# R, 117 bytes

function(d){while(!numbers::isPrime(y(d))){d=d-1};d}
<=format
y=function(d)sum(as.integer(c(d<"%Y",d<"%m",d<"%d")))


Try it online!

# F#, 134 133 bytes

let rec s(d:System.DateTime)=
let x=d.Year+d.Month+d.Day
if(Seq.tryFind(fun i->x%i=0){2..x-1}).IsNone then d else d.AddDays(-1.)|>s


-1 byte thanks to from sundar.

Try it online!

Total the day, month and year and see if it's prime. If it is, return that date. If not, decrement the date by 1 day and try again.

• You can save a byte by writing -1.0 as -1., in the AddDays call. – sundar Jun 24 '18 at 15:05
• You're right... that's really weird. But useful. Thanks. – Ciaran_McCarthy Jun 24 '18 at 21:43

# PowerShell, 105 90 bytes

for($a=$args[0];'1'*((Date $a -f yyyy+MM+dd)|iex)-match'^(..+)\1+$';$a=$a.AddDays(-1)){}$a  Try it online! Thanks to sundar for -13 bytes. Takes input as a DateTime 2018-06-20 and saves it into $a. Then we're in a for loop. Each iteration, we're taking $a -formatted like yyyy+MM+dd (i.e., the current date we're on separated by + signs) added together with |iex (similar to eval), string-multiplying that with 1s to form a unary number, and using a prime-checking regex to determine if the current date is prime or not. If it is not prime, we .AddDays(-1) to go backwards a day and continue the loop. If it is prime, we break out of the loop and place $a onto the pipeline with implicit output.

The resulting output is culture-dependent. On TIO, which uses en-us, the output is long-date format, which looks like Saturday, July 1, 1319 12:00:00 AM.

• You can save a few bytes by sending the argument as a datetime object. Also, the regex can be simplified to match composites above 2 (since minimum date is 0001-01-01 whose sum is 3). I took a crack at these changes here. – sundar Jun 20 '18 at 18:51
• (note though that I'm a powershell newbie and that linked code is only minimally tested, haven't even tried all the test cases from here.) – sundar Jun 20 '18 at 18:52
• @sundar I thought about that input, but it seemed a little "cheaty" to me, so I went with string input instead. Thanks for the tip on the regex -- I don't fully understand how it works, so I just smile and nod when it comes up. Hehe. – AdmBorkBork Jun 20 '18 at 19:55

# Bash, 114 108 bytes

a=date +%s -d$1 while [ "date +%d+%m+%Y -d@$a|bc|factor|awk NF!=2" ]
do a=$[a-86400] done date +%F -d@$a


Try it online!

My first ever bash golf. Honestly, my first real bash program ever ... primality test taken from here.

This might sometimes fail if there is a timezone change, but TIO uses UTC, so there it should work.

• Is the " 9" in the first line a typo? Removing that and the quotes around it (since we can require that the input must not contain spaces), and adding an a at the end after @\$, gives working code at 110 bytes. – sundar Jun 20 '18 at 19:19
• @sundar I thought that there might be problems with daylight saving time, but I will check that tomorrow again – wastl Jun 20 '18 at 20:11

# C (gcc), 167 bytes

r;P(n,i){for(r=0;++i<n;)r|=n%i<1;}f(y,m,d){for(;P(y+m+d,1),r;)!--d?d=" >8><><>><><>"[!--m?y--,m=12:m]/2+(m==2&!(y%4)&y%100|!(y%400)):0;printf("%04d-%02d-%02d",y,m,d);}


Try it online!

## Rundown

r;P(n,i){for(r=0;++i<n;)r|=n%i<1;}


The anti-prime-checking function. Since the earliest valid year we need to deal with is 0001-01-01, the lowest number we ever need to worry about is 3, so the special-case checks for n==2 or n < 2 are stripped out. r is set to a truthy value if n is not a prime. r is kept global, since not having to return it saves two bytes (i=n; to return vs ,r to check the global). i is set to 1 by the function caller, to save another 2 bytes.

f(y,m,d){for(;P(y+m+d,1),r;)


We take the date as three separate integers and start the main loop, which goes on until y+m+d is prime. Then we come to the meat of the function:

!--d?                           Decrement day and check if zero, which means we go back to last day of previous month.
d=" >8><><>><><>"               The string contains the number of days of each month times 2, to bring them into printable ASCII range.
We begin the string with a space, to avoid having to substract from index later.
[!--m?y--,m=12:m]/2+            Decrement month and check if zero. If so, go back a year and set m to 12. Use m as index in string.
(m==2&!(y%4)&y%100|!(y%400))    If the new month is February, add 1 to day if it's a leap year.
:0;                             Do nothing if day did not become zero.


It might seem iffy to use m and y both in the leap year check and as the index of the string, when the evaluation order is unspecified. Luckily, we only check for leap year if m == 2, which can't happen at the same time as we change m and y, since that only happens going from January to December, so the leap year check is never bothered by the order of evaluation.

Finally, the result is printed to STDOUT:

printf("%04d-%02d-%02d",y,m,d);}


# C# - 281239 232 Char

using System;class P{static void Main(){var d=DateTime.Parse(Console.ReadLine());do{int c=d.Year+d.Month+d.Day;if(c%2!=0){int i=3;for(;i<=c;i+=2)if(c%i==0)break;if(i>=c)break;}d=d.AddDays(-1);}while(d>DateTime.MinValue);Console.WriteLine(d);}}


ungolfed:

using System;
class P
{
static void Main()
{
do
{
int c = d.Year + d.Month + d.Day;
// minimum datetime in c# is 0001-01-01
// therefore do not need to check for the first two primes
int i = 3;
for (; i < c; i += 2) if (c % i == 0) break;
// check to break the date decrement loop if counter passed the input value
// ie, no factor could be found
if (i >= c) break;

} while (d > DateTime.MinValue);
Console.WriteLine(d);
}
}


Made the code less efficient but smaller. Prime loop will now go up to the integer rather than the square root. It will also process all even numbers.

• You can probably remove public. Also, since it doesn't seem to be disallowed to get the date input as a calling parameter, you could have Main(string[]a) and then DateTime.Parse(a[0]) – Corak Jun 26 '18 at 13:07

# MATL, 14 bytes

tsZp?.}YOqZOT


Try it online!

Alternately:

### 15 bytes

tsZp~tbYOw-ZOw


Try it online!