# Solution to "Party Time!"

The shortest distance from marker 1 to marker 2452 is 56 miles, making you arrive at the party 4 minutes early at 2:56pm. You get there fastest using the following directions (L for Left, S for Straight, and R for Right):

2-S, 2-R, L, S, 50-R

for a mile marker progression of 1, 2, 5, 6, 7, 49, 2402, 2403, 2404, 2405, ..., 2450, 2451, 2452.

In general, given a marker $n$, we want to work backwards and take the biggest jumps possible. That is, from $n$ to $\sqrt{n}$ if $n$ is a square, or decrement to the first square plus one then inverse of square plus one if $n$ is not a square. For example, if we are at marker 51, first we would have to travel one mile to marker 50, then one more to 7 (since from 7 you can square plus one to get to 50), for a total of 2 miles. So if $n$ is not a perfect square, then the distance from $n$ to the greatest perfect square less than or equal to $n$ is

which is the same as the number of miles from $n$ to after its first big "jump." For example,

If, on the other hand, $n$ is a perfect square, then the biggest jump it can make is by taking the inverse of the square path for one mile to $\sqrt{n}$ which can be expressed similarly to the previous formula,

This can be incorporated into a recursive algorithm to write into a programming language. I formulated one equation which covered both conditions above. To do so then I needed something that would equal 1 if $n$ is perfect square, or 0 otherwise. So total distance $f(n)$ to natural number mile marker $n$ I found could be expressed recursively by:

and a stopping value of

Below you will find my program in C++. Please note this was one of the first programs I wrote outside of my first class in C++, so it is not very elegant!

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

int main()
{
double n=0, distance=0, temp=0, temp2=0;
vector<char> turns;
cout<<"\nPlease enter mile marker number for the party: ";
cin>>n;
while(n<=0) //just a check for valid input
{
cout<<"\n**Negative mile marker invalid, please check again: ";
cin>>n;
}

cout<<"Distance to mile marker "<<n<<" is: ";

while(n>=2)
{
temp=floor(sqrt(n+0.5))-floor(sqrt(n-0.5));
temp2=n-floor(sqrt(n))*floor(sqrt(n));
distance=distance+temp2+temp;
if(temp==0) //if not a perfect square
{
for(unsigned int i=1;i<temp2;i++)
turns.push_back('R');
turns.push_back('S');
}
else if(temp==1)
turns.push_back('L');

n=floor(sqrt(n)); //recursion (more or less)
}

cout<<distance<<" miles.\n";
if(distance!=0)
{
cout<<"Take this route: ";

int turns_size=turns.size(), count=1;

for(int j=turns_size; j>=1; j--) //print directions
{
if(turns[j-2]!=turns[j-1]) //if different turns than next, print turn
{
if (count==1)
cout<<turns[j-1];
else
cout<<count<<"-"<<turns[j-1]; //coefficient number of turns
if(j>=2)
cout<<", ";
else
cout<<endl<<endl;
count=1;
}
else
count++;
}
}
else
cout<<endl;

return 0;
}