text:
Change the Timezone
Challenge
Given a time and a timezone as input, output the time in that timezone.
Time
The time will be given in 24 hour format like so:
hh:mm

Where hh is the two digit hour and mm is the two digit minute. Note that the hour and the minute will always be padded with zeroes like so:
06:09

All the times given are at UTC+00:00.
The hours in your output do not have to be padded wih zeroes but your time it must be in 24 hour format
Timezone
The timezone will be given in the following format:
UTC±hh:mm

Where ± is either going to be a + or a - and hh, is the two digit hour and mm is the two digit minute (again, these will be padded with zeroes).
To find the time in that timezone, you either add (if the symbol is +) or subtract (if the symbol is -) the time after the UTC± from the inputted time.
For example, if the input was 24:56 and UTC-02:50, you would subtract 2 hours and 50 minutes from 24:56:
24:56
02:50 -
-----
22:06

The output would be 22:06.
Examples
Chicago
Input:  08:50 and UTC-06:00
Output: 02:50

Kathmandu
Input:  09:42 and UTC+05:45
Output: 15:27

Samoa
Input:  06:42 and UTC+13:00
Output: 19:42

Hawaii
Input:  02:40 and UTC-10:00
Output: 16:40

Note that this has gone to the previous day.
Tokyo
Input:  17:25 and UTC+09:00
Output: 02:25

Note that this has gone to the following day.
Rules
You must not use any built in date functions or libraries.
Assume all input will be valid times and time offsets.
The timezone will be in the range UTC-24:00 to UTC+24:00 inclusive.
In the case of half past midnight, the correct representation should be 00:30, not 24:30.
Winning
The shortest code in bytes wins.

What about TimeSpan/Duration methods/classes? I assume those are also excluded

Also will input values always be valid times? Ie 26:02 and 08:74 would not appear? Same for the UTC offsets?

@pinkfloydx33 1) Yes, all of those excluded. 2) Assume all input is valid

Do we have to pad the output with zeroes? (eg. Can the last test case output 2:25)

@Loovjo No, the output does no have to be padded

24:54 or 00:54? Also is UTC+14:00 a valid input?

Shouldn't the second test case be 15:27?

@betseg 00:24 and I've added a range of acceptable time offsets

Please add a test case for MART and/or NST.

@Neil May I ask why? Surely the same principle is demonstrated by the Kathmandu time

If the output doesn't need to be padded would a time like 1:5 be valid instead of 1:05? I'd think only the hours shouldn't be padded. Also your example with 24:56 should that not be 00:56 since you've stated a range up to 24:00 and express similar in your half past midnight scenario?

Is the time guaranteed to be the first input, or can the inputs be in either order?

@BetaDecay In case an answer subtracts 3 hours but then and adds 30 minutes by mistake.

@Tortoise Post it as a non-competing entrant, if you like :) Just remember to put non-competing in the header

Could the input be a single string such as "17:25 UTC+09:00"?

@Arnauld Your input may be taken in anyway you wish, as long is follows the format given in the question

APL (Dyalog APL), 45 bytes
Expression
Takes two strings as right argument.
24 60⊤∘⍎∘⍕('+-'∩⍕),'/',(0 60⊥2⊃':'⎕VFI ¯5∘↑)¨

Try it online!
Explanation
24 60⊤ the number-to-base-a24b60 conversion
∘ of
⍎ the evaluation
∘ of
⍕ the formatted (i.e. flattened with separating spaces)
('+-'∩⍕) intersection of "+-" and the formatted input (this extracts the plus or minus)
, followed by
(...)¨ the following for each of the inputs (the time and the offset)
 0 60⊥ the a∞b60-to-number conversion of
 2⊃ the second element of
 ':'⎕VFI  the, using colon as field separator, Verified and Fixed Input of
 ¯5∘↑ the last five characters ("hh:mm")
Step-by-step on "17:25" and "UTC+09:00"
The left-side expression on the right side data, gives the data of the next line.

                       '17:25' 'UTC+09:00'
                      /     /   \         \
(...)¨ applies the function train to both inputs
                    /     /       \         \
¯5∘↑               '17:25'         'UTC+09:00'
':'⎕VFI            '17:25'         '09:00'
2⊃            (1 1)(17 25)         (1 1)(9 0)
0 60⊥                17 25         9 0
                      1045         540
                       \  \       / /
This is where ¨ stops, and execution continues on the resulting list
                         \  \   / /
'/',                      1045 540
('+-'∩⍕),             '/' 1045 540
⍕                 '+' '/' 1045 540
⍎                   '+ / 1045 540'
24 60⊤                        1585
                              2 25

C, 109 bytes
a,b,c;f(char*t,char*z){for(c=0;z[3];t=z+=3)sscanf(t,"%d:%d",&a,&b),c+=b+a*60;printf("%d:%02d",c/60%24,c%60);}

Invoke as follows:
int main() { f("17:25", "UTC+09:00"); }

How does this work for negative time offsets e.g. UTC-03:30?

Oops, I forgot about those, but thankfully, it’s an easy fix.

JavaScript (ES6), 101 bytes
(t,z,g=s=>+(s[3]+s[7]+s[8])+s.slice(3,6)*60,m=g('UTC+'+t)+g(z)+1440)=>(m/60%24|0)+':'+(m/10%6|0)+m%10

Would be 121 bytes if I padded the hours.

Python 2, 129 bytes
def T(t,a):f=[int.__add__,int.__sub__]["-"in a];m=f(int(t[3:5]),int(a[7:9]));print`f(int(t[0:2])+m/60,int(a[4:6]))%24`+":"+`m%60`

Call as T("02:45", "UTC-05:33")

Missing leading zeros in formatted output. Should say Python 2 in heading. Could reduce to a one line function with ;.

@JonathanAllan You don't need padding zeroes,

Ah, cool, missed that bit! Thanks

Python 2, 84 bytes
def f(t,z):i=int;r=60*(i(t[:2])+i(z[3:6]))+i(t[3:])+i(z[3]+z[7:]);print r/60%24,r%60

All test cases are at ideone
Output format is space separated, with no leading zeros.

Java 201 bytes
String T(String t,String z){return(24+Integer.valueOf(t.substring(0,2))+Integer.valueOf((String)z.subSequence(3,6)))%24+":"+(60+Integer.valueOf(t.substring(3,5))+Integer.valueOf(z.substring(7,9)))%60;}

Called as
    T("12:00", "UTC+02:40")
Unglolfed for the logic,
String T(String t, String z) {
    int i = (24 + Integer.valueOf(t.substring(0, 2)) + Integer.valueOf((String) z.subSequence(3, 6))) % 24;
    int j = (60 + Integer.valueOf(t.substring(3, 5)) + Integer.valueOf(z.substring(7, 9))) % 60;
    return i + ":" + j;
}

Any help to get it under 200 would be appreciated!

This is flawed. Doesn't fulfil the 2nd test (where the hour is incremented). Also, to reduce, why do you use subSequence instead of substring? To golf more, declare Integer i=1; and replace all other Integer by i, so you have i.valueOf instead of Integer.valueOf.

@OlivierGrégoire huh? Could you elaborate on the second test please!

For the Kathmandu test case, you output 14:27 instead of 15:27.

@OlivierGrégoire ah good point

Or even java.util.function.Function v=Integer::valueOf. Not sure if that would actually save much.

You could also do something tricky like interface V{int a(String s);} then in your function V v=Integer::valurOf, then each valueOf would be reduced to v.a. Not sure if worth it over the Integer i=1 approach

You can replace the four Integer.valueOf(...) to new Long(...) (PS / FYI: Both Integer.decode(...) and new Integer(...) are also shorter than Integer.valueOf(...), and there is also a fourth option to parse String to an integer which is longer: Integer.parseInt(...).)

@KevinCruijssen Integer.decode(String) won't work with values like 09. new Integer(String) is longer if Womba fixes his issues mentioned in comment 1.

Javascript (ES6), 93 92 bytes
t=>((t=eval(t.replace(/.*?(.)?(..):(..)/g,'$1($2*60+$3)+720')))/60%24|0)+':'+(t/10%6|0)+t%10

Test cases

let f =
t=>((t=eval(t.replace(/.*?(.)?(..):(..)/g,'$1($2*60+$3)+720')))/60%24|0)+':'+(t/10%6|0)+t%10

console.log(f("08:50 UTC-06:00")); //  2:50
console.log(f("09:42 UTC+05:45")); // 15:27
console.log(f("06:42 UTC+13:00")); // 19:42
console.log(f("02:40 UTC-10:00")); // 16:40
console.log(f("17:25 UTC+09:00")); //  2:25

Ruby, 95 bytes
g=->s{"60*"+s.scan(/\d+/).map(&:to_i)*?+}
f=->t,z{r=eval(g[t]+z[3]+g[z]);print r/60%24,?:,r%60}

Usage
f[gets,gets]

Inputs(example)
08:50
UTC-06:00

C# 214 205 183 Bytes
string f(char[]t,char[]u){int s=~(u[3]-45),z=48,m=(t[3]-z)*10+t[4]-z+((u[7]-z)*10+u[8]-z)*s,h=(t[0]-z)*10+t[1]-z+((u[4]-z)*10+u[5]-z)*s+m/60+(m>>8)+24;return$"{h%24}:{(m+60)%60:D2}";}

205 byte version
string f(string t,string u){Func<string,int>P=int.Parse;var T=t.Split(':');int s=u[3]<45?1:-1,m=P(T[1])+P(u.Substring(7))*s,h=P(T[0])+P($"{u[4]}"+u[5])*s+m/60+(m<0?-1:0)+24;return$"{h%24}:{(m+60)%60:D2}";}

Ungolfed
string f(char[] t, char[] u)
{
    int s = ~(u[3]-45),
        z = 48,
        m = (t[3] - z) * 10 + t[4] - z + ((u[7] - z) * 10 + u[8] - z) * s,
        h = (t[0] - z) * 10 + t[1] - z + ((u[4] - z) * 10 + u[5] - z) * s + m / 60 + (m>>8) + 24;
    return $"{h % 24}:{(m + 60) % 60:D2}";
}

Original 214:
string f(string t,string u){Func<string,int>P=int.Parse;var T=t.Split(':');int h=P(T[0]),m=P(T[1]),s=u[3]<45?1:-1;m+=P(u.Substring(7))*s;h+=P($"{u[4]}"+u[5])*s+m/60+(m<0?-1:0)+24;return$"{h%24:D2}:{(m+60)%60:D2}";}

Java 156 150 149 147 142 bytes
t->z->{Integer H=100,T=H.valueOf(t.replace(":","")),Z=H.valueOf(z.replace(":","").substring(3)),c=(T/H+Z/H+24)*60+T%H+Z%H;return c/60%24+":"+c%60;}

Test cases & ungolfed
import java.util.function.BiFunction;

public class Main {
    public static void main(String[] args) {

        BiFunction<String,String,String> f = (t,z)->{
            Integer H = 100, // Hundred, used several times, shorter as variable
                    T = H.valueOf(t.replace(":","")), // as int (HHMM)
                    Z = H.valueOf(z.replaceAll("[UTC:]","")), // as int (-HHMM)
                    c = (T/H + Z/H + 24) * 60 + T%H + Z%H; // transform into minutes
            return c/60%24+":"+c%60;
        };

        test(f, "08:50", "UTC-06:00", "02:50");
        test(f, "09:42", "UTC+05:45", "15:27");
        test(f, "03:42", "UTC-05:45", "21:57");
        test(f, "06:42", "UTC+13:00", "19:42");
        test(f, "02:40", "UTC-10:00", "16:40");
        test(f, "17:25", "UTC+09:00", "02:25");
    }

    private static void test(BiFunction<String,String,String> f, String time, String zone, String expected) {
        // Padding is allowed. Make sure the padding is skipped for the test, then.
        String result = String.format("%2s:%2s", (Object[])f.apply(time, zone).split(":")).replace(" ","0");
        if (result.equals(expected)) {
            System.out.printf("%s + %s: OK%n", time, zone);
        } else {
            System.out.printf("%s + %s: Expected \"%s\", got \"%s\"%n", time, zone, expected, result);
        }

    }
}

Shavings

150 -> 149: a/H*60+b/H*60 -> (a/H+b/H)*60
149 -> 147: (T/H+Z/H)*60+1440 -> (T/H+Z/H+24)*60.
147 -> 142: z.replace(":","").substring(3) -> z.replaceAll("[UTC:]","")

CJam, 40 bytes
r{':/60b}:F~r3>(\F\~1440,=60b{s2Te[}%':*

Try it online! (As a test suite.)
Explanation
r           e# Read first input (time).
{':/60b}:F  e# Define a function F, which splits a string around ':' and
            e# treats the two elements as base-60 digits.
~           e# Run that function on the first input.
r3>         e# Read the second input and discard the 'UTC'.
(           e# Pull off the +-.
\F          e# Apply F to the timezone offset.
\~          e# Execute the + or - on the two amounts of minutes.
1440,=      e# Modulo 1440 to fit everything into the 24-hour format.
60b         e# Obtain base 60 digits again.
{s2Te[}%    e# Convert each digit to a string and pad it to 2 decimal digits.
':*         e# Join them with a ':'.

Retina, 100 bytes
:
59$*:,
+`(\d+):
$1,$1
\d+
$*
T`1`0`-.+
^
1440$*
+`10|\D

1{1440}

^(1{60})*(.*)
$#1:$.2
\b\d\b
0$&

Try it online!
Explanation
:
59$*:,

Replaces each : with 59 of them and a comma as a separator.
+`(\d+):
$1,$1

Repeatedly duplicates the number in front of a :. So the first two stages multiply the hour-value by 60.
\d+
$*

Convert each number to unary.
T`1`0`-.+

If there's a minus sign in the input, then this transliteration stage turns all the 1s after it into 0s. We're basically using 0 as a unary -1 digit here.
^
1440$*

Insert 1440 1s (i.e. a full day). This is to ensure that the time doesn't get negative.
+`10|\D

This repeatedly removes all non-digits (i.e. the space, the UTC, the + or -, as well as all the , we've inserted) and the 10 combination, thereby cancelling positive and negative digits. This basically subtracts the second number from the first if it's negative, or adds it otherwise.
1{1440}

Removes 1440 1s if possible (basically taking the result modulo 1440 to fit it into a single 24 hours).
^(1{60})*(.*)
$#1:$.2

Decompose the number into hours and minutes by matching as many chunks of 60 digits as possible (counting the chunks with $#1) followed by the remaining digits (whose length is counted with $.2).
\b\d\b
0$&

If there are any single digits in the result, prepend a zero.


text:
Goldenness of an integer
A positive integer n can be represented as a rectangle with integer sides a, b such that n = a * b. That is, the area represents the number. In general, a and b are not unique for a given n.
As is well known, a rectangle is specially pleasing to the eye (or is it the brain?) when its sides are in the golden ratio, φ = (sqrt(5)+1)/2 ≈ 1.6180339887...
Combining these two facts, the purpose of this challenge is to decompose an integer n into the product of two integers a, b whose ratio is as close as possible to φ (with the usual metric on ℝ). The fact that φ is irrational implies that there is a unique solution pair (a, b).
The challenge
Given a positive integer n, output positive integers a, b such that  a * b = n and the absolute difference between a/b and φ is minimized.
As an example, consider n = 12. The pairs (a, b) that satisfy a * b = n are: (1, 12), (2,6), (3,4), (4,3), (6,2), (12,1). The pair whose ratio is closest to φ is (4,3), which gives 4/3 = 1.333.
Rules
Functions or programs are acceptable.
The numerator (a) should appear first in the output, and the denominator (b) second. Other than that, input and output formats are flexible as usual. For example, the two numbers can be output as strings with any reasonable separator, or as an array.
The code should work in theory for arbitrarily large numbers. In practice, it may be limited by memory or data-type restrictions.
It's sufficient to consider an approximate version of φ, as long as it is accurate up to the third decimal or better. That is, the absolute difference between the true φ and the approximate value should not exceed 0.0005. For example, 1.618 is acceptable.
When using an approximate, rational version of φ there's a small chance that the solution is not unique. In that case you can output any pair a, b that satisfies the minimization criterion.
Shortest code wins.
Test cases
1        ->  1    1
2        ->  2    1
4        ->  2    2
12       ->  4    3
42       ->  7    6
576      ->  32   18
1234     ->  2    617
10000    ->  125  80
199999   ->  1    199999
9699690  ->  3990 2431

Surely most answers will be using some sort of rational approximation to φ, unless you accept e.g. the answer with the result of a/b-b/a is as close to 1 as possible.

@Neil I'm not sure I understand your comment. Your idea of minimizing |a/b-b/a-1| is promising, although a proof would be in order

Not sure that I can cram a whole proof into a comment, but the outline is as follows: the whole rectangle represents a/b. Removing the unit square leaves the small rectangle on the right which represents b/a. A golden rectangle therefore achieves a difference of 1.

If a and b aren't adjacent numbers in the Fibbonacci sequence, is there any point including them in the test?

That said, 1618 x 1000 seems like a good candidate (or, by reference, 809 x 500)

@Strawberry I don't follow. Why would it only make sense to include Fibonacci numbers?

Thinking about it, it doesn't. The fibonnaci sequence is a subset of the group of 'quite golden' numbers.

Jelly, 16 15 14 bytes
Saved 1 byte thanks to @miles.
÷/ạØp
ÆDżṚ$ÇÞḢ

Try it online!
Explanation
÷/ạØp         Helper link, calculates abs(a/b - phi). Argument: [a, b]
÷/            Reduce by division to calculate a/b.
  ạØp         Calculate abs(a/b - phi).

ÆDżṚ$ÇÞḢ      Main link. Argument: n
ÆD            Get divisors of n.
  żṚ$         Pair the items of the list with those of its reverse. The reversed
              divisors of a number is the same list as the number divided by each
              of the divisors.
     ÇÞ       Sort by the output of the helper link of each pair.
       Ḣ      Get the first element [a, b] and implicitly print.

You can save a byte by interleaving the reverse of the divisor list with itself. Using ÷/ạØp¶ÆDżṚ$ÇÞḢ for 14 bytes, it returns a list [a, b] given n as an argument.

@miles Cool! I apparently completely missed on /. (This is what I did in my Pyth solution.) Will edit when I get on my laptop.

Pyth - 24 23 bytes
There has to be a better way to find the divisors...
ho.a-.n3cFNfsIeTm,dcQdS

Test Suite.

Not any shorter, but much faster: hoa.n3cFNm,d/Qdm*Fdty+1P. Tests

Matlab, 96 81 bytes
Golfed (-15bytes), props to Luis Mendo
function w(n);a=find(~(mod(n,1:n)));[~,c]=min(abs(a./(n./a)-1.618));[a(c) n/a(c)]

Original:
function w(n)
a=find(not(mod(n,1:n)));b=abs(a./(n./a)-1.618);c=find(not(b-min(b)));[a(c) n/a(c)]

This is by far not a great solution, but my first attempt at code-golf. What fun!

Agreed that it's fun! Welcome to the site!

You can replace not by ~  to save a few bytes. Also, using the second output of min you can get rid of find: a=find(~(mod(n,1:n)));[~,c]=min(abs(a./(n./a)-1.618));[a(c) n/a(c)]

Well spotted - that shaves off quite some symbols!

You can make it shorter by using n=input(''); instead of function w(n); then you have an extra pair of () around the mod.

Mathematica, 51 bytes
#&@@SortBy[{x=Divisors@#,#/x},Abs[#/#2-1.618]&]&

The  is Mathematica's postfix operator for transposition (displayed as a superscript T in Mathematica).
Mathematica has a built-in GoldenRatio, but 1.618 is a lot shorter, especially because the former also requires N@.

05AB1E, 21 bytes
Code:
ÑÂø©vy`/})5t>;-ÄWQ®sÏ

Uses the CP-1252 encoding. Try it online!

Javascript (ES6), 73 bytes
n=>{for(b=0,k=n/.809;n%++b||k>b*b*2&&(a=b););return[b=k-a*a>b*b?b:a,n/b]}

We look for:

a = highest divisor of n for which n / φ > a²
b = lowest divisor of n for which n / φ < b²

Then, the solution is either [ a, n / a ] or [ b, n / b ]. We compare n / φ - a² with b² - n / φ to find out which expression is closest to zero.
The actual formula used in the code are based on φ / 2 which can be written in a shorter way than φ with the same precision: .809 vs 1.618.
Therefore:

n / φ > a² ⇔ n / (φ / 2) > 2a²

and:

n / φ - a² > b² - n / φ ⇔ 2n / φ - a² > b² ⇔ n / (φ / 2)
  - a² > b²

Complexity
The number of iterations heavily depends on the number of factors of n. The worst case occurs when n is prime, because we have to perform all iterations from 1 to n to find its only 2 divisors. This is what happens with 199999. On the other hand, 9699690 is 19-smooth and we quickly find two divisors on either sides of the breaking point √(n/φ) ≈ 2448.
Test cases

let f =
n=>{for(b=0,k=n/.809;n%++b||k>b*b*2&&(a=b););return[b=k-a*a>b*b?b:a,n/b]}

console.log(JSON.stringify(f(12)));       // [ 3, 4 ]
console.log(JSON.stringify(f(42)));       // [ 6, 7 ]
console.log(JSON.stringify(f(576)));      // [ 18, 32 ]
console.log(JSON.stringify(f(1234)));     // [ 2, 617 ]
console.log(JSON.stringify(f(10000)));    // [ 80, 125 ]
console.log(JSON.stringify(f(199999)));   // [ 1, 199999 ]
console.log(JSON.stringify(f(9699690)));  // [ 2431, 3990 ]

Pyth, 21 20 18 bytes
hoacFN.n3C_Bf!%QTS

Try it online. Test suite.
Explanation

Get the incluSive range from 1 to input.
filter for numbers for that divide the input !%QT.
Get [that list, that list reversed] _B. The reversed divisors of a number is the same list as the number divided by each of the divisors.
Transpose the list to get pairs of [numerator, denominator].
Sort the pairs by the absolute difference of the ratio of the pair cFN and the golden ratio .n3.
Get the first (lowest) pair h and print.

JavaScript (ES6), 83 bytes

f=
n=>{p=r=>Math.abs(r/n-n/r-1);for(r=i=n;--i;)r=n%i||p(i*i)>p(r*r)?r:i;return[r,n/r]}
;
<input type=number min=1 oninput=[a.value,b.value]=f(+this.value)><input readonly id=a><input readonly id=b>

Actually returns the (a, b) pair which minimises the absolute value of a/b-b/a-1, but this works for all the test cases at least, although I guess I could save 4 bytes by using the 1.618 test instead.

Brachylog, 41 bytes
:1fL:2a:Lzoht
,A:B#>.*?!,.=
:3a/:$A-$|
//

Try it online!
Explanation

Main predicate:
:1fL           L is the list of all couples [A:B] such that A*B = Input (see Pred. 1)
    :2a        Compute the distance between all As/Bs and φ (see Pred. 2)
       :Lz     Zip those distances to L
          o    Sort the zip on the distances
           ht  Take the couple [A:B] of the first element of the sorted list

Predicate 1: Output is a couple [A:B] such that A*B = Input
,A:B           The list [A:B]
    #>         Both A and B are strictly positive
      .        Output = [A:B]
       *?      A*B = Input
         !,    Discard other choice points
           .=  Assign a value to A and B that satisfy the constraints

Predicate 2: Compute the distance between A/B and φ.
:3a            Convert A and B to floats
   /           Divide A by B
    :$A-       Subtract φ
        $|     Absolute value

Predicate 3: Convert an int to a float by inverting its inverse
/              1/Input
 /             Output = 1/(1/Input)

Out of curiosity: is φ a predefined literal in Brachylog? Or where is it defined in the code?

Oh, I just saw: $A

@LuisMendo A for Au ;)

Aaah, very nice!

Haskell (Lambdabot), 86 bytes
f(x,y)=abs$(x/y)-1.618
q n=minimumBy((.f).compare.f)[(x,y)|x<-[1..n],y<-[1..n],x*y==n]

php, 103 bytes
<?php for($s=$a=$argv[1];++$i<$a;)if($a%$i==0&&$s>$t=abs($i*$i/$a-1.618)){$n=$i;$s=$t;}echo"$n ".$a/$n;

Produces a notice (this doesn't interrupt execution) about unassigned $i so should be run in an environment that silences notices.

Counting the PHP open tag is not needed when the code can be run as php -r '…' (where -r is for free). And definitely no need for the long form, as short_open_tag is on by default.

As far as I know $argv doesn't work with -r so this can't be run like that anyway. That said changing it to readline() or fgets(STDIN) if you're on windows and running without the tag is probably shorter anyway.

-r and $argv are working well together: http://pastebin.com/vcgb5pT2

Huh. Well it doesn't work for me, I just get undefined variable notices, I wonder if it's a setting or if it's just windows as per usual.

You can still replace <?php with <? to save three bytes.

Python 3, 96 bytes
Pretty simple solution. Makes use of this SO answer.
lambda n:min([((i,n//i),abs(1.618-i/(n//i)))for i in range(1,n+1)if n%i<1],key=lambda x:x[1])[0]

Try it online
The same solution in Python 2 is one byte longer.
lambda n:min([((i,n/i),abs(1.618-1.*i/(n/i)))for i in range(1,n+1)if n%i<1],key=lambda x:x[1])[0]

source: Stack Exchange

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

sort: votes


text:
Can the number reach 1 by repeatedly subtracting the largest prime less than it?
Challenge:
Given a number, take the largest prime strictly less than it, subtract it from this number, do this again to this new number with the biggest prime less than it, and continue doing this until it's less than 3. If it reaches 1, your program should output a truthy value, else, the program should output a falsey value.
Examples:
All of these should give a truthy value:
3
4
6
8
10
11
12
14
16
17
18
20
22
23
24
26
27
29
30
32
34
35
37
38
40
41
42
44
46
47
48
50

All of these should give falsey values:
5
7
9
13
15
19
21
25
28
31
33
36
39
43
45
49

Rules:

You can either write a program or function.
You can assume that the input is bigger than 2.
Standard loopholes apply
This is code-golf so the shortest answer wins!

related http://oeis.org/A175071

5-3=2, 2-(-2)=4, 4-3=1. (/wiseguy)

@Hurkyl -2 = -1×2, so it's not prime ;-)

@ETHProductions: Ah, but -1 is a unit; that factorization doesn't contradict the primality of -2 any more than 2=(-1)×(-2) does of 2. (or even 2=1×2)

@ETHproductions - just to clarify further, primes are numbers that cannot be expressed as the product of two or more other primes, but that also can't divide 1. If they can divide 1, they are called units, not primes. Both 1 and -1 are units.

@Hurkyl - shame the question specifies "until it's less than 3". Otherwise, you'd be right.

@GlenO Thanks for the explanation. Out of curiosity, does this mean that 1/2, -1/2, etc. are also units, or does this rule only apply to integers?

@ETHproductions - it doesn't only apply to integers, but it doesn't apply to the rational numbers under the normal definitions of addition and multiplication. In fact, if you're considering the rational numbers (rather than the integers), then no number is prime.

@ETHproductions: The rational numbers are interesting because there are two very different approaches that are useful in practice! The rational numbers has no primes (not even 2!) because everything is a unit. However, you can also view the rationals as a construction made from the integers and study them using the primes of the integers. (e.g. anyone asking for the prime factorization of 9/10 as 2^(-1) 3^2 5^(-1) is thinking in terms of the latter)

@Hurkyl Fascinating! Thanks for educating me. So by the latter thinking, is 1/p always prime if p is prime?

Jelly, 9 8 bytes
’ÆRṪạµ¡Ḃ

Try it online! or verify all test cases.
How it works
’ÆRṪạµ¡Ḃ  Main link. Argument: n

     µ    Combine all atoms to the left into a chain.
’           Decrement; yield n - 1.
 ÆR         Prime range; yield all primes in [2, ..., n -1].
   Ṫ        Tail; yield p, the last prime in the range.
            If the range is empty, this yields p = 0.
    ạ       Compute the absolute difference of p and n.
      ¡   Call the chain to the left n times.
          This suffices since each iteration decreases n, until one of the fixed
          points (1 or 2) is reached.
       Ḃ  Bit; return the parity of the fixed point.

Retina, 31 bytes
.+
$*
+`1(?!(11+)\1+$)11+
1
^1$

Prints 0 (falsy) or 1 (truthy).
Try it online! (The first line enables a linefeed-separated test suite.)
Explanation
.+
$*

Convert input to unary by turning input N into N copies of 1.
+`1(?!(11+)\1+$)11+
1

Repeatedly remove the largest prime less than the input. This is based on the standard primality test with regex.
^1$

Check whether the result is a single 1.

How is it that you can use Retina without unary? O.o

@Syxer the first two lines convert the input to unary.

Doesn't that mean you can remove them and request unary input?

@Syxer I could, but I sort of stopped doing that. It seems like a dodgy I/O format, and now that the conversion is 6 bytes (as opposed to the ~200 it used to be), I don't think Retina counts as "can't reasonably take input in decimal".

Ah, I see. I've only ever seen unary input in Retina, thus my confusion.

Regex (ECMAScript or better), 33 32 bytes
^((?=.+?(?=(xx+?)\2*$)\2$)\2)*x$

Takes its input in unary, as a string of x characters whose length represents the number.
Try it online! - ECMAScript
Try it online! - Java
Try it online! - Perl
Try it online! - PCRE
Try it online! - Boost
Try it online! - Python
Try it online! - Ruby
Try it online! - .NET
I finally found a use for the positive lookahead primality test I came up with on 2018-12-07! This is 2 bytes longer than the "standard" negative lookahead primality test, but it allows the full regex to be 1 byte shorter:
^                           # tail = input number
(                           # Loop the following:
    (?=                     # Atomic lookahead - finds the first match, and once
                            # finished, its result won't be changed by backtracking
        .+?                 # tail = largest number that is less than the current tail,
                            #        for which the following matches:
        (?=(xx+?)\2*$)\2$   # Assert tail is prime; \2 = tail
    )
    \2                      # tail -= \2
)*                          # Iterate the above loop zero or more times
x$                          # Assert tail==1

A neat thing about this regex is that it can be logically negated for all inputs other than zero simply by adding one byte, because  after the repeated subtraction, all \$n>0\$ end up at either \$1\$ or \$2\$:
^((?=.+?(?=(xx+?)\2*$)\2$)\2)*xx$

Try it online! - ECMAScript
Try it online! - Java
Try it online! - Perl
Try it online! - PCRE
Try it online! - Boost
Try it online! - Python
Try it online! - Ruby
Try it online! - .NET

Here is the regex implemented in some languages that have golf-efficient regex calls, where it either beats the other submitted solution(s) or is the only one in that language:
\$\large\textit{Anonymous functions}\$
Julia v0.4+, 58 bytes
n->split("x"^n,r"^((?=.+?(?=(xx+?)\2*$)\2$)\2)*x$")[1]==""

Try it online!
The above returns truthy for an input of 0. If returning falsey for 0 were needed, it'd be 60 bytes:
n->match(r"^((?=.+?(?=(xx+?)\2*$)\2$)\2)*x$","x"^n)!=nothing

Try it online!
or 59 bytes in Julia v0.7 and earlier with !=Void(): Try it online!
Of course as far as Julia v0.4 goes, Glen O's answer outgolfs this at 32 bytes, but for v0.5 and later, this and the below may be optimal golf.
Julia v0.7+, 54 bytes
n->occursin(r"^((?=.+?(?=(xx+?)\2*$)\2$)\2)*x$",'x'^n)

Try it online!
Julia v1.2+, 53 bytes
n->endswith('x'^n,r"^((?=.+?(?=(xx+?)\2*$)\2$)\2)*x")

Attempt This Online!
PowerShell, 52 51 bytes
'x'*"$args"-match'^((?=.+?(?=(xx+?)\2*$)\2$)\2)*x$'

Try it online!
-1 bytes thanks to Julian
Python, 70 69 bytes
lambda n:re.match(r'((?=.+?(?=(xx+?)\2*$)\2$)\2)*x$','x'*n);import re

Try it online!
Python, 73 bytes
lambda n:__import__('re').match(r'((?=.+?(?=(xx+?)\2*$)\2$)\2)*x$','x'*n)

Try it online!
(If it must be a pure lambda.)
JavaScript (ES6), 58 54 bytes
n=>/^((?=.+?(?=(..+?)\2*$)\2$)\2)*.$/.test(Array(n+1))

Try it online!
-4 bytes thanks to a technique used by RK. and CubeyTheCube
Perl, 49 47 bytes
-2 bytes thanks to dingledooper
sub{1x pop~~/^((?=.+?(?=(..+?)\2*$)\2$)\2)*.$/}

Try it online!
This beats a port of Ton Hospel's 41 byte answer (57 bytes):
sub{my$x=1x pop;$x=$`while$x=~/\B(?!(11+)\1+$|$)|11$/;$x}

Try it online!
Even if it's allowed to modified the global variable $_ (51 bytes):
sub{$_=1x pop;$_=$`while/\B(?!(11+)\1+$|$)|11$/;$_}

Try it online!
Ruby, 48 45 bytes
->n{?x*n=~/^((?=.+?(?=(xx+?)\2*$)\2$)\2)*x$/}

Try it online!
-2 bytes by switching the truthy value from "string of x characters whose length is the input number" to "the integer value 0", while keeping the same falsey value of nil
-1 byte by using ?x instead of "x"
PHP, 89 75 71 bytes
fn($n)=>preg_match('/^((?=.+?(?=(..+?)\2*$)\2$)\2)*.$/',str_pad('',$n))

Try it online!
-4 bytes by switching from x to   as the repeated character
R, 73 72 68 63 bytes
\(n)grepl('^((?=.+?(?=(..+?)\\2*$)\\2$)\\2)*.$',strrep(1,n),,1)

Attempt This Online! / Try it online!
\(n)grepl('^((?=.+?(?!(..+)\\2+$)(..+))\\3)*.$',strrep(1,n),,1)

Attempt This Online! / Try it online!
-1 byte thanks to Giuseppe
-4 bytes by using grepl() instead of sum(grep()) or any(grep())
-5 bytes by using a new anonymous function syntax introduced in R v4.1.0
Since TIO uses R v3.5.2, the TIO links have the old 68 byte versions of the function.
Java 8, 92 89 88 71 bytes
n->new String(new char[n]).matches("((?=.+?(?=(..+?)\\2*$)\\2$)\\2)*.")

Try it online!
n->new String(new char[n]).matches("((?=.+?(?!(..+)\\2+$)(..+))\\3)*.")

Try it online!
-17 bytes by just matching the regex straight against a string of NUL characters instead of replacing the NULs with x
Java 11, 61 bytes
n->"x".repeat(n).matches("((?=.+?(?=(xx+?)\\2*$)\\2$)\\2)*x")

Try it online!
-10 bytes relative to Java <11, thanks to Kevin Cruijssen
\$\large\textit{Full programs}\$
Python 2, 69 bytes
import re
re.match(r'((?=.+?(?=(xx+?)\2*$)\2$)\2)*x$','x'*input()).re

Outputs via its exit code, value 0 for truthy (by exiting normally), and 1 for falsey (by triggering an AttributeError).
Try it online!
Python 2, 71 70 bytes
import re
re.match(r'((?=.+?(?=(xx+?)\2*$)\2$)\2)*xx$','x'*input()).re

Outputs via its exit code, value 1 for truthy and 0 for falsey, using the truth-inverted regex.
Try it online!
Alternative method using the uninverted regex, outputting exit code 1 for truthy (by triggering a NameError), and 0 for falsey (by exiting normally), at 71 bytes:
import re
if re.match(r'((?=.+?(?=(xx+?)\2*$)\2$)\2)*x$','x'*input()):z

Try it online!
Python 2, 79 74 bytes
import re
print re.match(r'((?=.+?(?=(xx+?)\2*$)\2$)\2)*x$','x'*input())>0

Outputs True or False via stdout.
Try it online!
Python 3, 84 83 bytes
import re
print(not re.match(r'((?=.+?(?=(xx+?)\2*$)\2$)\2)*xx$','x'*int(input())))

Try it online!
The above uses the truth-inverted regex. Without it is 84 bytes:
import re
print(bool(re.match(r'((?=.+?(?=(xx+?)\2*$)\2$)\2)*x$','x'*int(input()))))

Try it online!
PHP -F, 70 bytes
<?=preg_match('/^((?=.+?(?=(..+?)\2*$)\2$)\2)*.$/',str_pad('',$argn));

Try it online!
Perl -p, 45 43 bytes
-2 bytes thanks to dingledooper
$_=1x$_~~/^((?=.+?(?=(..+?)\2*$)\2$)\2)*.$/

Try it online!
Beaten by Ton Hospel's 41 byte answer which mixes regex and code: Try it online!
Perl, 46 44 bytes
say 1x<>~~/^((?=.+?(?=(..+?)\2*$)\2$)\2)*.$/

Try it online!
Now beats a port of Ton Hospel's answer (45 bytes):
$_=1x<>;$_=$`while/\B(?!(11+)\1+$|$)|11$/;say

Try it online!

Amazing that these are the shortest answers here for many of these languages, even with the function definition and regex match overhead, etc.

One character shorter in PowerShell

Pyth, 18 15 14 bytes
Thanks to @Maltysen for -1 byte
#=-QefP_TUQ)q1

A program that takes input on STDIN and prints True or False as appropriate.
Try it online
How it works
#=-QefP_TUQ)q1  Program. Input: Q
#          )    Loop until error statement (which occurs when Q<3):
         UQ      Yield [0, 1, 2, 3, ..., Q-1]
     fP_T        Filter that by primality
    e            Yield the last element of that
 =-Q             Q = Q - that
            q1  Q is 1 (implicit variable fill)
                Implicitly print

Old version with reduce, 18 bytes
qu-G*<HGH_fP_TSQQ1

Try it online
How it works
qu-G*<HGH_fP_TSQQ1  Program. Input: Q
              SQ    Yield [1, 2, 3, ..., Q]
          fP_T      Filter that by primality
         _          Reverse it
 u                  Reduce it:
                Q    with base case Q and
                     function G, H ->
     <HG              H<G
    *   H             *H (yields H if H<G, else 0)
  -G                  Subtract that from G
q                1  The result of that is 1
                    Implicitly print

St is U 15 chars

13 bytes

Julia (0.4), 32 bytes
(Update (as of 1.4): This is rather out-of-date, now - primes is no longer in Base, and ?: needs spaces around the ? and the :)
While it's not going to be the shortest solution among the languages, this might be the shortest of the human-readable ones...
!n=n>2?!(n-primes(n-1)[end]):n<2

Try it online!
Or, to put it in slightly clearer terms
function !(n)
  if n>2
    m=primes(n-1)[end]   # Gets largest prime less than n
    return !(n-m)        # Recurses
  else
    return n<2           # Gives true if n is 1 and false if n is 2
  end
end

Called with, for example, !37.

JavaScript (ES6), 64 63 bytes
Saved 1 byte thanks to @Neil
g=(x,n=x-1)=>n<2?x:x%n?g(x,n-1):g(x-1)
f=x=>x<3?x%2:f(x-g(x-1))

I wrote this in 2 minutes... and it worked perfectly the first time. First user to find the inevitable bug wins....
Try it out

g=(x,n=x-1)=>n<2?x:x%n?g(x,n-1):g(x-1)
f=x=>x<3?x%2:f(x-g(x-1))
<input type="number" value=3 min=3 onchange="A.innerHTML=f(this.value)">

1

How it works
First we define g(x) as the function that finds the first prime number p <= x. This is done using the following process:

Start with n = x-1.
If n < 2, x is prime; return x.
If x is divisible  by n, decrement x and go to step 1.
Otherwise, decrement n and go to step 2.

The solution to this challenge, f(x), is now fairly straightforward:

If x < 3, return x = 1.
Otherwise, subtract g(x-1) and try again.

4326, which should return true does not seem to return, but 4328 (true) and 4329 (false) do, is this a JS limitation or a bug?

@JonathanAllan 4326 throws too much recursion to the browser console in Firefox 48, so I guess the recursion passes FF's recursion limit.

Yep, next prime down is 4297 (and next up is 4327), which will be why 4328 works.

x%2 should save you a byte over x==1.

@Neil I would never have thought of that :-)

@Neil, ooo... this will save me a byte in another question. +1

@JonathanAllan If you want an iterative version, I came up with x=>[1,1,...Array(x)].map((c,i,b)=>(a[i]=a[i-p],c||b.map((_,j)=>b[j]|=j%i<1,p=i)),a=[,1],p=0)&&a[x] - it's a bit long though.

@Neil I was just wondering what the reason was, it's fine to have correct code that only fails due to a recursion limitation IMO; but nice stuff!

Pyke, 15 11 bytes
WDU#_P)e-Dt

Try it here!
            - stack = input
W           - while continue:
  U#_P)     -     filter(is_prime, range(stack))
       e    -    ^[-1]
 D      -   -   stack-^
         Dt -  continue = ^ != 1

Returns 1 if true and raises an exception if false

Husk, 11 9 bytes
εωλ-→fṗŀ¹

Try it online!
-2 bytes from Leo.
None of the testcases reach zero because the max number we can subtract from n can only be n-1. Hence, we can check insignificance instead of equality with 1.
Explanation
εωλ-→fṗŀ¹
 ωλ       iterate on the input till fixpoint
       ŀ¹  range 0..n-1
     fṗ    filter out nonprimes
    →      last element
   -       subtract from n
ε         is fixed point insignificant? (<= 1?)

Can be shortened by iterating until fixed point: Try it online!

Python3, 102 92 90 89 88 bytes
f=lambda n:n<2if n<3else f(n-[x for x in range(2,n)if all(x%y for y in range(2,x))][-1])

Golfing suggestions welcome! I see that gmpy contains a function next_prime, but I can't test it yet :(
-2 bytes, thanks to @JonathanAllan!
-1 byte, thanks to @Aaron!
Testcases
f=lambda n:n<2if n<3else f(n-[x for x in range(2,n)if all(x%y for y in range(2,x))][-1])

s="3 4 6 8 10 11 12 14 16 17 18 20 22"
h="5 7 9 13 15 19 21 25 28 31 33 36 39"

for j in s.split(" "):print(f(int(j)))
for j in h.split(" "):print(f(int(j)))

Output is 13 truthy values and 13 falsey values.
s contains the truthy cases and h the falseys.

if all(x%y for... works

n<3 else -> n<3else to get same length as mine ;)

Haskell, 65 63 bytes
f n|n>2=f$n-last[p|p<-[2..n-1],all((>0).mod p)[2..p-1]]|1>0=n<2

Try it online!

Mathematica, 32 bytes
2>(#//.x_/;x>2:>x+NextPrime@-x)&

This is an unnamed function which takes an integer and returns a boolean.
Explanation
There's a lot of syntax and funny reading order here, so...
   #                               This is simply the argument of the function.
    //.                            This is the 'ReplaceRepeated' operator, which applies
                                   a substitution until the its left-hand argument stops
                                   changing.
       x_/;x>2                     The substitution pattern. Matches any expression x as
                                   long as that expression is greater than 2.
              :>                   Replace that with...
                  NextPrime@-x     Mathematica has a NextPrime built-in but no
                                   PreviousPrime built-in. Conveniently, NextPrime
                                   works with negative inputs and then gives you the
                                   next "negative prime" which is basically a
                                   PreviousPrime function (just with an added minus sign).
                x+                 This gets added to x, which subtracts the previous
                                   prime from it.
2>(                           )    Finally, we check whether the result is less than 2.

Closely beats #+0~Min~NextPrime@-#&~FixedPoint~#==1& (36 bytes). Nice use of //. !

@GregMartin 35 when you use <2 at the end.

Python, with sympy, 60 bytes
import sympy
f=lambda n:n>2and f(n-sympy.prevprime(n))or n<2

My previous method was 83 bytes without sympy using recursion, but I took truthy/falsey to mean distinguishable and consistent, but I have been informed that's an incorrect interpretation. I can't seem to salvage it due to the tail, but I'll leave it here in case someone knows how to do so:
f=lambda n,p=0:n>2and(any(p%x==0for x in range(2,p))and f(n,p-1)or f(n-p,n+~p))or n

2 is not a falsey value.

@mbomb007 I thought specs are "true or false" if that is required, whereas "truthy or falsey" means distinguishable and consistent?

Nope. They are defined as we decided on the meta site. Any question that allows "distinguishable and consistent" output must specify that, rather than truthy/falsey.

OK I read this, will update at some point...

APL (Dyalog Unicode), 27 bytes
{⍵<3:⍵=1⋄∇⍵-⊃⌽(⊢~∘.×⍨)2↓⍳⍵}
 ⍵<3 ⍝ Termination condition
   :⍵=1 ⍝ return value
     ⋄ ⍝ Separator
       ∇ ⍝ Recursive call
         ⍵-⊃⌽ ⍝ Subtract largest prime
           (⊢~∘.×⍨) ⍝ Calculate primes less than argument
             2↓⍳⍵ ⍝ Range 2–(N-1)

Try it online!

Brachylog, 11 bytes
1|-↙Xṗ∧X≜!↰

Try it online!
1              The input is 1,
 |             or:
       X≜      X is the integer with the least absolute value such that
  -↙X          it is positive, and if it is subtracted from the input
     ṗ∧        the result is prime.
         !     Consider no other value of X.
          ↰    Call this predicate again with X as the input.

Vyxal, 7 bytes
‡∆ṗεẊ1=

Try it Online!
Very nice and neat answer (flagless too!)
Explained
‡∆ṗεẊ1=
‡∆ṗε    # lambda x: abs(x - prev_prime(x))
    Ẋ   # repeat that on the input until it doesn't change
     1= # does that equal 1?

What's even more surprising is that this still works. You can save a byte with either ∷ or ₂ instead of 1=

CJam, 21 16 bytes
Thanks to Dennis for saving 4 bytes.
ri{_1|{mp},W=-}h

Try it online!
Explanation
ri       e# Read input and convert to integer N.
{        e# Run this block as long as N is positive (or until the program aborts
         e# with an error)...
  _1|    e#   Duplicate and OR 1. This rounds up to an odd number. For N > 2, this
         e#   will never affect the greatest prime less than N.
  {mp},  e#   Get all primes from 0 to (N|1)-1.
         e#   For N > 2, this will contain all primes less than N.
         e#   For N = 2, this will contain only 2.
         e#   For N = 1, this will be empty.
  W=     e#   Select the last element (largest prime up to (N|1)-1).
         e#   For N = 1, this will result in an error and terminate the program, which
         e#   still prints the stack contents though (which are 1, the desired output).
  -      e#   Subtract from N. Note that this gives us 0 for N = 2, which terminates the
         e#   loop.
}h

ri_{_1|{mp},W=-}* should work.

@Dennis Thanks, the 1| is really clever. :) (And I always forget that {...}, does an implicit range...)

.NET Regex, 38 bytes
Just to show that it can be checked in a single regex.
^(?>(?<=(.*))..+(?<!^\1\2+(.+.)|$))+.$

Input is assumed to be in unary.
Explanation
It simply implements the requirement to the word, repeatedly removing the biggest prime and check whether there remainder is 1.

(?>(?<=(.*))..+(?<!^\1\2+(.+.)|$))+: Non-backtracking group makes sure the biggest prime we found is not overriden, and + simply repeat the process of matching the biggest prime.

(?<=(.*))..+(?<!^\1\2+(.+.)|$): Match the biggest prime less than the remaining number

(?<=(.*)): Record how much we have subtracted to establish an "anchor" point for assertion.
..+: Look for the biggest number...
(?<!^\1\2+(.+.)|$): ... which is prime and less than the remaining number.

(?<!^\1\2+(.+.)): The usual prime test routine, with ^\1 tacked in front to make sure we are checking the amount matched by ..+
(?!<$): Assert less than the remaining number

The (?<=(.*)) part is rather clumsy. Not sure if there is a better way. Also, I'm curious if there is a solution in PCRE.

What in the....

I think this is a case of when you have a hammer (lookbehind), every problem looks like a nail :-) I've been guilty of the same. But it can be done in 32 bytes in any engine supporting positive lookahead.

Python 2.7: 88 87 Bytes
r=lambda n:n>2and r(n-[a for a in range(2,n)if all(a%b for b in range(2,a))][-1])or n<2

Thx @TuukkaX for -1 more byte!

Update your description ;) Also, you could save one byte by saying n<2 instead of n==1.

Try it online!

86 bytes

MATL, 13 bytes
`tqZq0)-t2>}o

Try it online! Or verify all test cases at once.
Explanation
`        % Do...while
  t      %   Duplicate. Takes input implicitly in the first iteration
  qZq    %   All primes less than that
  0)     %   Get last one
  -      %   Subtract (this result will be used in the next iteration, if any)
  t      %   Duplicate
  2>     %   Does it exceed 2? If so: next iteration. Else: execute the "finally"
         %   block and exit do...while loop
}        % Finally
  o      %   Parity. Transforms 2 into 0 and 1 into 1
         % End do...while implicitly
         % Display implicitly

Perl, 42 bytes
Includes +1 for -p
Run with input on STDIN
reach1.pl:
#!/usr/bin/perl -p
$_=1x$_;$_=$`while/\B(?!(11+)\1+$|$)|11$/

Uses the classic primality regex

Factor + math.primes, 51 bytes
[ [ dup 1 - primes-upto last - dup 2 > ] loop 1 = ]

Try it online!

Vitsy, 28 26 bytes
This can definitely be shortened.
<]xN0)l1)-1[)/3D-];(pD-1[D

<                    Traverse the code in this direction, rotating on the line.
                     For the sake of reading the code easier, I'm reversing the
                     code on this line. This will be the order executed.

 D[1-Dp(;]-D3/)[1-)1l)0Nx]
 D                         Duplicate the top member of the stack.
  [      ]                 Do the stuff in brackets until break is called.
   1-                      Subtract 1 from the top item of the stack.
     D                     Duplicate the top member of the stack.
      p(                   If the top member is a prime...
        ;                  break;
          -                Pop a, b, push a - b.
           D3/)[         ] If this value is less than 3, do the bracketed code.
                1-         Subtract the top item of the stack by 1.
                  )        If the top item is zero...
                   1       Push 1.
                    l)     If the length of the stack is zero...
                      0    Push 0.
                       N   Output the top member of the stack.
                        x  System.exit(0);

Try it online!

Floroid, 45 30 29 bytes
f=Bb:b<2Fb<3Gf(b-en(b-1)[-1])

Perl 6,  54 53 52  51 bytes
{($_,{$_-($_-1...2).first: *.is-prime}...3>*)[*-1]==1}
{($_,{$_-($_-1...2).first: *.is-prime}...3>*).any==1}
{any($_,{$_-($_-1...2).first: *.is-prime}...3>*)==1}

{any($_,{$_-(^$_).grep(*.is-prime)[*-1]}...3>*)==1}

Explanation:
# bare block lambda with implicit parameter ｢$_｣
# used to generate all of the rest of the elements of the sequence
{
  # create an any Junction of the following list
  any(
    $_, # initialize sequence with the inner block's argument

    # bare block lambda with implicit parameter ｢$_｣
    {
      # take this inner block's argument and subtract
      $_ -

      ( ^$_ )            # Range up-to and excluding ｢$_｣
      .grep(*.is-prime)\ # find the primes
      [ * - 1 ]          # return the last value
    }

    ...   # keep doing that until

    3 > * # the result is less than 3

  # test that Junction against ｢1｣
  # ( returns an ｢any｣ Junction like ｢any(False, False, True)｣ )
  ) == 1
}

Example:
# show what is returned and if it is truthy
sub show ($_) {
  # ｢.&{…}｣ uses the block as a method and implicitly against ｢$_｣
  my $value = .&{any($_,{$_-(^$_).grep(*.is-prime)[*-1]}...3>*)==1}
  say join "\t", $_, ?$value, $value.gist;
}

show 3;  # 3    True    any(False, True)
show 4;  # 4    True    any(False, True)
show 5;  # 5    False   any(False, False)
show 10; # 10   True    any(False, False, True)
show 28; # 28   False   any(False, False, False)
show 49; # 49   False   any(False, False)
show 50; # 50   True    any(False, False, True)

Irregular, 63 bytes
p~?1_$-1p:;
n=i(0)?1_$-1p:;
_~
N=n
1(?!(11+)\1+$)11+~1
^11$~0
N

I created this language two days ago, and the basic premises are that there are no built in loops, the only features are basic arithmetic and decision making, and program evaluation is based on regular expressions.
Explanation
p~?1_$-1p:;
n=i(0)?1_$-1p:;
_~
N=n

This part converts the input into unary. It repeatedly subtracts 1 from the input until it equals 0, prepending 1_ each time. It then removes all of the _s. If I hadn't forgotten a break in my code it could be written as so:
p~?1_$-1p:;
_~
n=i(0)?1_$-1p:;

The next part repeatedly removes the largest prime from the input until it is equal to 1 or 11, with 11 being replaced with 0.
1(?!(11+)\1+$)11+~1
^11$~0
N

I used the regex from Martin Ender's answer.

PowerShell v2+, 81 bytes
param($n)while($n-gt2){$n-=(($n-1)..2|?{'1'*$_-match'^(?!(..+)\1+$)..'})[0]}!--$n

Takes input $n. Enters a while loop so long as $n is still 3 or greater. Each iteration, subtracts a number from $n. The number is  the results of the regex primality test applied against a range ($n-1)..2 via the Where-Object (?) operator, then the first [0] of the results (since the range is decreasing, this results in the largest one being selected). After concluding the loop, $n is either going to be 1 or 2, by definition, so we pre-decrement $n (turning it into either 0 or 1), and take the Boolean-not ! thereof. That's left on the pipeline and output is implicit.
Examples
PS C:\Tools\Scripts\golfing> 3..20|%{"$_ --> "+(.\can-the-number-reach-one.ps1 $_)}
3 --> True
4 --> True
5 --> False
6 --> True
7 --> False
8 --> True
9 --> False
10 --> True
11 --> True
12 --> True
13 --> False
14 --> True
15 --> False
16 --> True
17 --> True
18 --> True
19 --> False
20 --> True

Clojure, 125 bytes
#(loop[x %](if(> x 2)(recur(- x(loop[y(dec x)](if(some zero?(vec(for[z(range 2 y)](mod y z))))(recur(dec y))y))))(quot 1 x)))

Yikes, that is one long piece of code. The most verbose language strikes again!
Ungolfed:
(defn subprime [n]
  (loop [x n]
    (if (> x 2)
      (recur
        (- x
          (loop [y (dec x)]
            (if (some zero? (vec (for [z (range 2 y)] (mod y z))))
              (recur (dec y)) y))))
      (quot 1 x))))

05AB1E, 7 bytes
ΔD<ÅPà-

Outputs 2 as falsey (only 1 is truthy in 05AB1E).
Try it online or verify all test cases.
Explanation:
Unfortunately the previous prime builtin ÅM goes into an infinite loop for \$\leq2\$, otherwise it could have been used to save a few bytes.
Δ        # Loop until the result no longer changes:
 D       #  Duplicate the current value
         #  (which is the implicit input-integer in the first iteration)
  <ÅP    #  Pop it, and push a list of all primes < this value:
  <      #   Decrease the value by 1
   ÅP    #   Pop and push a list of all primes <= this value-1
     à   #  Pop and push the maximum prime of this list
         #  (or an empty string if the list is empty)
      -  #  Subtract it from the value (where subtracting the empty string is a no-op)
         # (after which the found result is output implicitly)

Ooh, very convenient for this challenge that 05AB1E's booleans work that way.

@Deadcode Yep, sometimes it can be useful that only 1 is truthy in 05AB1E. Not just with outputs, but also with filters and such. :) But if a 1/0 was expected as result, it would only cost 2 bytes: } to close the loop, and Θ, the 05AB1E-style truthify (basically an ==1 check, returning 0 for everything else).

Haskell, 79 bytes
Not really short but pointfree :)
(<2).until(<3)(until(flip(`until`(+1))2.(.)(<1).mod>>=(==))pred.pred>>=flip(-))

Matlab, 51 bytes
v=@(x)x-max(primes(x-1));while(x>=3)x=v(x);end;x==1

This is VERY similar to the JS6 solution by ETHProductions, but needs the variable to be in the workspace.

authors: n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳

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

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


text:
Hyperprogramming: N+N, N×N, N^N all in one
Write a program that takes in a number N from 1 to 9 inclusive. In its native form your program should output N+N. E.g. output 2 if N is 1, 4 if N is 2, 6 if N is 3, and so on.
When every character in your program is duplicated in place, then it should be a program that takes in N (still from 1 to 9) and outputs N×N. E.g. output 1 if N is 1, 4 if N is 2, 9 if N is 3, and so on.
When every character in your program is triplicated in place, then it should be a program that takes in N (still from 1 to 9) and outputs N^N. E.g. output 1 if N is 1, 4 if N is 2, 27 if N is 3, 387420489 if N is 9, etc.
Numbers above 9 aren't required because 10^10 is outside of many language's usual integer range.
Example
If your initial program was
My_Program!
Exit();

Then it should be capable of taking in N and outputting N+N.
Additionally, the program
MMyy__PPrrooggrraamm!!

EExxiitt(());;

should take in N and output N×N.
Finally, the program
MMMyyy___PPPrrrooogggrrraaammm!!!

EEExxxiiittt((()));;;

should take in N and output N^N.
Quadrupled-character programs and beyond are not required.
Rules

Input and output should be plain, normally formatted decimal numbers. You may answer using a different base to show off your code but then your answer is non-competitive.

Windows users may treat \r\n as one character since things like \r\r\n\n wouldn't make sense or perhaps even work.

The shortest native program (the N+N one) in bytes wins.

is it even possible?

It always seems impossible until it's done - Nelson Mandela

@SargeBorsch Yes.

Unfortunately it's only possible in limited amount of languages.

Can we create a program that asks for multiple inputs once run as duplicated/triplicated, and then assume that input is given only to 1 of those 2 or 3 prompts?

@R.Kap No, seems too confusing.

Jelly, 12 bytes
N+N
“(ẹ+)‘FQṖṪỌv

Try it online!
N×N
““((ẹẹ++))‘‘FFQQṖṖṪṪỌỌvv

Try it online!
N^N
“““(((ẹẹẹ+++)))‘‘‘FFFQQQṖṖṖṪṪṪỌỌỌvvv

Try it online!
How it works
Jelly has several different types of string literals; all of them start with a “. If the literal contains more than one “, a string array is returned, and “ separates the strings from each other.
For example, “abc“def” yields ['abc', 'def'].
Depending on the last character of the literal (any of ”«»‘’, where « is currently unimplemented), one can choose between the different types of literals. For ‘, we get the code points in Jelly's code page instead of the corresponding Unicode characters.
For example, “abc“def‘ yields [[97, 98, 99], [100, 101, 102]].
The three literals in the programs correspond to the following code point arrays.
“(ẹ+)‘           -> [40, 214, 43, 41]
““((ẹẹ++))‘      -> [[], [40, 40, 214, 214, 43, 43, 41, 41]]
“““(((ẹẹẹ+++)))‘ -> [[], [], [40, 40, 40, 214, 214, 214, 43, 43, 43, 41, 41, 41]]

N+N
“(ẹ+)‘FQṖṪỌv                          Main link. Argument: n

“(ẹ+)‘                                As before.
      F                               Flatten the array. Yields an integer array.
       Q                              Unique; deduplicate the integers.
                                      This yields [40, 214, 43, 41].
        Ṗ                             Pop; remove the last element.
         Ṫ                            Tail; extract the last element.
                                      This yields 43, the Unicode code point of +.
          Ọ                           Unordinal; cast to character.
           v                          Eval; execute the character as a Jelly
                                      program with argument n.

N×N
““((ẹẹ++))‘‘FFQQṖṖṪṪỌỌvv              Main link. Argument: n

““((ẹẹ++))‘                           As before.
           ‘                          Increment all integers.
            FF                        Flatten the array. Yields an integer array.
              QQ                      Unique; deduplicate the integers.
                                      This yields [41, 215, 44, 42].
                ṖṖ                    Pop twice; remove the last two elements.
                  ṪṪ                  Tail; extract the last element.
                                      This yields 215, the Unicode code point of ×.
                    ỌỌ                Unordinal; cast to character.
                      v               Eval; execute the character as a Jelly
                                      program with argument n.
                       v              Eval; convert the return value (n×n) to a
                                      string and execute that string as a Jelly
                                      program with argument n. Since the string
                                      consists of a single integer literal, that
                                      integer is returned, ignoring the argument.

Note that F, Q, Ṫ, and Ọ do not alter 1D arrays, arrays without duplicates, integers, and characters (respectively).
N^N
“““(((ẹẹẹ+++)))‘‘‘FFFQQQṖṖṖṪṪṪỌỌỌvvv  Main link. Argument: n

“““(((ẹẹẹ+++)))‘                      As before.
                ‘‘                    Increment all integers twice.
                  FFF                 Flatten the array. Yields an integer array.
                     QQQ              Unique; deduplicate the integers.
                                      This yields [42, 216, 45, 43].
                        ṖṖṖ           Pop thrice; remove the last three elements.
                           ṪṪṪ        Tail; extract the last element.
                                      This yields 42, the Unicode code point of *.
                              ỌỌỌ     Unordinal; cast to character.
                                 v    Eval; execute the character as a Jelly
                                      program with argument n.
                                  vv  Eval twice. See N×N.

I did expect an answer, because you guys here can solve anything, but this is just some really crazy stuff. You are a master and I'm in awe of your magnificence.

I don't think I've seen an answer from Dennis before that doesn't result in me starting off thinking "no way", then slowly being convinced that he's some sort of god by reading the explanation.

Joined to upvote. Wow.

No way... how many hours a day do you spend in golfing?!?

A question like this... and not even 6 hours ???

@Falco I'm sure Dennis was just asleep when it was posted. ;)

If this answer is not sexy, I don't know what is .. :)

I just applaud for this answer. Just look at the explanation; how does Dennis find these answers?

><>, 41 bytes
\<
1:: :
&&* +
i*n n
c&
%:
4l
0(
.i
n}
&?

Try it online: N+N, N*N, N^N. Assumes that the STDIN input is exactly one char.
 ><> is a 2D language, so we can make use of the fact that code semantics are mostly unchanged if we execute instructions downwards — the extra empty lines that ensue are just no-ops. The exception to this is the conditional trampoline ? which pops a value and skips the next instruction if the value was nonzero — the extra newlines would mess up ? due to the inserted no-ops, but we can get around this by putting the ? at the end of a column and taking advantage of wrapping.
To decide which operation to execute, the key is 40., which teleports the IP to position (4, 0). Due to the expansion of the code, the x = 4 column corresponds to + for the base program, * for the doubled program and ^ for the tripled program. Unfortunately ><> doesn't have exponentiation built in, making that the bulk of the program.
[Setup]
\         Mirror: reflect IP direction to downwards
1&        Put 1 into the register
ic%       Push a code point of input, then take it mod 12. This maps the char '1' to the
          number 1, and so forth for '2' to '9'.
40.       Jump to (4, 0), still heading downwards

[N+N version]
:+        Duplicate then add
n         Output as number
          (Stack is now empty, so the program errors out trying to do the above again)

[N*N version]
:*        Duplicate then multiply
n         Output as number
          (Stack is now empty, so the program errors out trying to do the above again)

[N^N version]
:&*&      Multiply register by N
:l(       Push (N < length of stack + 1)
i         Push input, but since we're now at EOF this pushes -1 (stack length += 1)
}         Move -1 to the back
?<        If (N < length + 1) was 1, execute the < to move leftward. Otherwise, skip it.
          (Continue loop)

\         Mirror: reflect IP direction upwards
&n        Output register
.         Jump to (-1, N), which is invalid so the program errors out

TovTovTov (a mutation of Chicken): 810147050 bytes
Described below are two suggested solutions: One full solution to the question requiring lots of bytes, and a second partial solution (solving only the N+N and N*N parts, requiring only 484 bytes), each taking a different approach and its own set of cool tricks! :)
1. Full solution (810147050 bytes)
Using TovTovTov(TOV='hi',SEP=','), the TOV elements are immune to duplicating characters in place (both "hihihi" and "hhiihhiihhii" have three "hi"s in them, and all TovTovTov cares about is how many TOVs appear between SEPs).
If we used SEP=', ', the entire program would be immune to character duplication (which is cool, but won't solve the question). So we use SEP=','.
So the program "hihihi,hi", for example, compiles to the ints array [3,1], while "hhiihhiihhii,,hhii" compiles to [3,0,1] and "hhiihhiihhii,,hhii" to [3,0,0,1]. This means that the commands themselves don't change their meaning after duplication, but the overall length changes with character duplication. The solution below queries the length of the program and uses this to decide whether to print N+N, N*N or N^N.
The suggested full solution, as ints array, is: [6, 12, 9, 18, 9, 142, 11, 38, 8, 9, 260, 11, 73, 8, 22, 75, 7, 10, 14, 3, 1, 22, 24, 18, 15, 8, 10, 16, 3, 1, 22, 24, 18, 15, 8, 10, 45, 16, 7, 22, 3, 1, 22, 24, 18, 15, 8, 22, 3, 1, 22, 24, 18, 15, 8, 25, 3, 1, 22, 24, 18, 15, 8, 48, 3, 1, 22, 24, 18, 15, 8, 277, 3, 1, 22, 24, 18, 15, 8, 3146, 3, 1, 22, 24, 18, 15, 8, 46677, 3, 1, 22, 24, 18, 15, 8, 823564, 3, 1, 22, 24, 18, 15, 8, 16777237, 3, 1, 22, 24, 18, 15, 8, 387420510, 3, 1, 22, 24, 18, 15, 8]
As a string, it's a pretty long program, consisting of 810147050 characters, starting with:
hihihihihihi,hihihihihihihihihihihihi,hihihihihihihihihi,hihihihihihihihihihihihihihihihihihi,hihihihihihihihihi,hihihihihihihihihihihihihihihihihihihihihihihihihihihihihihihihihihihihihihihihihihihih...
2. Solving only the N+N and N*N parts of the question (484 bytes)
Using TovTovTov(TOV='1',SEP=', '), this time the SEPs are immune to duplication (",,  " still has just one ", " in it), so the following suggested solution will always have 33 commands in it, even after character duplication:
1111, 111111111111111111111111111111111111111111111111, 1111111111, 1111111111, 1111111111, 111111, 111111111111, 111111111, 11111111111111, 111, 1, 1111111111111111111111, 111111111111111111111111, 111111111111111111, 111111111111111, 11111111, 111111111111, 1111111111111111, 111111111111111, 1111111111111111111111, 111111111111111111111111111111111111, 11, 1111111111111111111111111111, 111111, 111, 111111, 11111111111, 111111111111111111111111111, 1111, 1, 11111111, 1, 11111111
The corresponding ints array (the number of TOVs (1s) in each of the 33 commands above) is as follows: [4,48,10,10,10,6,12,9,14,3,1,22,24,18,15,8,12,16,15,22,36,2,28,6,3,6,11,27,4,1,8,1,8]
Duplicating the characters in place results in a list of 33 totally different commands:
[8,96,20,20,20,12,24,18,28,6,2,44,48,36,30,16,24,32,30,44,72,4,56,12,6,12,22,54,8,2,16,2,16]
The original ints array (that calculates N+N) was designed carefully so that after the commands change their meaning, the program still makes sense, but calculates N*N. For example, the first 4 (that TovTovTov understands as "treat the next op as an ascii code to convert to a character") changes after character duplication to 8, which is a totally different command ("change the Program Counter to the first popped value from the stack, if the value popped immediately after is true").

Befunge-98 (FBBI), 38 41 bytes
(+3 bytes to fix bug, thanks Jo King!)
vx:k::1-k*\/.@
20@
j3.
>^*
>:^
>:+.@

Try it online: N+N, N*N, N^N
This program won't work out-of-the-box since it requires input to be on the stack at the start of execution. By replacing the first line with the following code (adding three more bytes) it will take input from stdin:
v
&x:k:2-

Explanation
Setup
v       Redirect motion downward
02j     Jump over two instructions/spaces, executing the third
        If N=1, it will skip to the 6th line
        If N=2, it will skip to the 5th line
        If N=3, it will skip to the 4th line

N=1
>       Move right
:+.@    Duplicate, add, print and exit

N=2
>>::^^  Move right, duplicate twice, move up
*.@     Multiply, print and exit

N=3
>>>^^^  Redirect motion
30x     Set instruction pointer delta to (3, 0), causing it to
        move right, executing every third instruction
:k::    Duplicate the number (we'll call it M) M+2 times
        The stack is now [M]*(M+3)
1-k*    Multiply things M times (`k' is a quirky instruction)
\/      Divide that result by M (workaround for `k` being quirky)
.@      Print and exit

Unfortunately N=3 doesn't work for input 2 (damn you k!). You can fix this with :k::1-k*\/.@ instead

@JoKing Thank you! I've updated the post.

Gol><>, 20 18 bytes
Unlike ><>, Gol><> actually has an exponentiation built-in.
\hh
I
:
\\
\\\
X*+

Try it online!
Try it online (doubled)!
Try it online (tripled)!
Explanation
For the explanations here, I'll replace un-executed code with spaces.
\      Reflect the pointer down
I      Take an input
:      Copy the input
\\     Series of mirrors...
 \\    That reflect to the addition part
  +    Add the two numbers
  h    (Wrapped around) Print, and Halt

Explanation (doubled)
\            Reflect down

I            Take input

:            Duplicate the stack

\\           Set of mirrors...

 \\          That redirect to the * section

  *          Multiply two numbers

  h          (Wrapped around) Print + Halt

Explanation (tripled)
\            Reflect down

I            Take input

:            Duplicate input

\\           Set of mirrors...

 \\          ... That redirect to the exponentiation section

  X          Exponentiate the two values

  \h         (Wrapped around) Reflect right to the Print + Halt statement

Gol><>, 19 bytes
A longer (and more boring) version based on the ><> solution.
v
IX* +
:hh h
4
0
.

Try it online!
Try it online (doubled)!
Try it online (tripled)!

Nice use of the reflects like that! :)

Itr, 29 bytes
"L0#+â*;"0 0 0'+$©^#$0ååä0 0^
online interpreter
doubled
tripled
Explanation
Relies on Itr's redefinition operator $ (and the ability to redefine redefinition) to distinguish between the first and third case.
Uses string literals to run independent code for the second case.
normal:
"L0#+â*;"0 0 0'+$©^#$0ååä0 0^
"L0#+â*;"                     ; string literal
         0 0 0                ; push zero 3 times
              '+$©^           ; redefine ^ to mean +
                   #$0        ; read the input, store it in variable zero
                      ååä     ; stack operations
                         0 0^ ; Input + Input (after redefinition)
                              ; implicit output

doubled:
""LL00##++ââ**;;""00  00  00''++$$©©^^##$$00ååååää00  00^^
""                ; empty string
  LL              ; push 1 two times (calling 'L' on number)
    00            ; push zero
      ##          ; read input, 2nd # will push zero as stdin is empty
        ++        ; add up the top 3 stack values (results in the input value)
          ââ      ; "under" stack operation twice (1 1 X -> 1 X X 1 X )
            **    ; multiply top three stack values, giving X*1*X=X*X
              ;;  ; comment out the rest of the line

tripled:
"""LLL000###+++âââ***;;;"""000   000   000'''+++$$$©©©^^^###$$$000ååååååäää000   000^^^

"""LLL000###+++âââ***;;;"""    ; 3 string literals

000   000   000                ; push zero 3 times

'''+++$$                       ; redefine the $ operator to be the string literal "R"

$©                             ; call "R" consuming zero on stack
  ©©                           ; call 3rd zero and empty string on stack
    ^^^                        ; power with basis zero -> will push (vector of) zeros

###$$$000ååååååäää000   000^^^ ; the actual computation
###                            ; read number and two implicit zero from stdin
   $$$                         ; push string "R" 3 times
      000                      ; push zero
         åååååå                ; discard the top 6 values on the stack
               äää             ; duplicate top stack value (Input) 3 times
                  000   000    ; push zero twice
                           ^^^ ; calculates X^(X^(0^0))= X^X


text:
Make me a bad fade animation... please
Your task is to, as the title discreetly suggests, make a bad fade animation of one word turning into a second word for yours truly.
What exactly is this "fade animation" you may ask?
To make a spectacular(ly bad) fade animation, you take two strings which will contain only printable ASCII characters. You start by printing your starting string (the first of the two). Then, you randomly pick a character in the original word and change it to the corresponding character in the word you want to animate to. When the words are of unequal length, you must pad them with spaces.
You keep on doing this until all of the characters have been changed, but you will not change the character at a certain index more than once. Here is an example i/o:
Hey -> Peeps
Hey    # original string
Hey s  # replace char at index 4
Hey s  # replace char at index 1
Pey s  # replace char at index 0
Pee s  # replace char at index 2
Peeps  # replace char at index 3

You must write a function or full program that changes a letter and then prints the new string at increments of one second. The input format is loose, but the output format is strict.
This is code-golf, so shortest code in bytes wins.
Some test cases (Form: init -> final):
Stringy -> Blingy
Banana -> Republic
United -> States
Make America -> Tissue box
I like walls -> I have small hands
Hello, -> world!

Reference implementation in Python 2:
import random
import time
def F(c,f):
    print c                                      # before we do stuff
    if len(c)>len(f):f+=" "*(len(c)-len(f))      # add padding part 1
    if len(f)>len(c):c+=" "*(len(f)-len(c))      # add padding part 2
    c, f = list(c), list(f)
    ai = [i for i in range(len(c))]              # a list for keeping track
    while len(ai) > 0:                           #  of available indices
        time.sleep(1)                            # 1 second pause...
        i = ai.pop(random.randint(0,len(ai)-1))  # get a random index and remove
        c[i] = f[i]                              #   it from the list
        print ''.join(c)                         # print the new string

Stinking infinite loops are forbidden by default. Nice-smelling ones, too.

I don't think the python code is valid? Because you have uncommented comments?

Any restriction on the string length?

@ConorO'Brien, oh yeah.... oops :p

@Titus, anything your language can handle I guess

You also might want to clearly specify that the strings are to be padded to the same length with spaces.

@ConorO'Brien — edited

Should Stingy -> Blingy be two replacements or six?

@Titus, 6 replacements and 7 prints total

Pyth - 25 24 bytes
Will refactor.
AC.tQdV.SU
G
=XGN@HN.d_1

Try it online here.

Ok, thanks for clarifying!

MATL, 33 bytes
cn2/XKZ@!Oyhg*XR"GcK:@mK:Eq+)D1Y.

Try it at MATL Online. You may need to refresh the page and press "Run" again if it doesn't work.
Alternatively, this version (35 bytes) deletes the screen before each new string is displayed, which results in the output being "modified in place":

Does this have the one second pauses? It doesn't run on my phone.

@Dopapp Yes, the final 1Y. is the pause within the loop. It works for me from my computer using Chrome

@Dopapp What operating system are you using?

@Suever, iOS 9.

@Dopapp Safari?

@Suever, yeah  .

@Dopapp If you want you can pop into the MATL chat to see if I can reproduce the issue.

@Suever is it supposed to work in Safari?

@Dopapp works for me in safari and chrome on iOS 9. You have to scroll to see the output though if your screen in smaller

@Suever, oh it's working now but not before for some reason. Maybe connectivity issues

@Dopapp we're still working out some of the issues so let us know if you have any more.

Python 2, 171 169 168 163 bytes
import time,random as r
def f(a,b):
 d=len(a)-len(b);a+=' '*-d;b+=' '*d;o=range(len(a));r.shuffle(o);print a
 for i in o:time.sleep(1);a=a[:i]+b[i]+a[i+1:];print a

Test cases are on ideone

Perl, 131 + 4 (-F -l) = 135 bytes
@T=@F if!$i++}$T[$_]||=$",$F[$_]||=$"for 0..$#F,0..$#T;say@T;{$==rand@T;redo if$h{$=}++;$T[$=]=$F[$=];sleep 1;say@T;redo if++$v!=@T

Needs -F and -l flags to run, as well as -M5.010 (or -E). Note that if your version of perl is a bit old, you'll need to add -an on your command line (which I'll add too bellow to show it, but it's not needed).
For instance :
$ cat fade.pl
@T=@F if!$i++}$T[$_]||=$",$F[$_]||=$"for 0..$#F,0..$#T;say@T;{$==rand@T;redo if$h{$=}++;$T[$=]=$F[$=];sleep 1;say@T;redo if++$v!=@T
$ perl -F -anl -M5.010 fade.pl <<< "Hey
Peeps"
Hey
Pey
Pee
Pee s
Pee s
Peeps

I'm pretty sure this could be shorter, but I couldn't find out how... yet! Still, I don't think this is a bad answer, and hopefully someone will be inspired to make it shorter (or have a totally different idea!).

C# 299 Bytes
void f(string a,string b){var m=Math.Max(a.Length,b.Length);var t=new Collections.Generic.HashSet<int>();while(t.Count<m)t.Add(new Random().Next()%m);var s=a.PadRight(m).ToCharArray();Console.WriteLine(s);foreach(var x in t){Threading.Thread.Sleep(1000);s[x]=b.PadRight(m)[x];Console.WriteLine(s);}}

Ungolfed
void f(string a, string b)
{
    var m = Math.Max(a.Length, b.Length);
    var t = new Collections.Generic.HashSet<int>();
    while(t.Count < m) t.Add(new Random().Next()%m);
    var s=a.PadRight(m).ToCharArray();

    Console.WriteLine(s);
    foreach (var x in t)
    {
        Threading.Thread.Sleep(1000);
        s[x] = b.PadRight(m)[x];
        Console.WriteLine(s);
    }
}

Perl, 109 108 99 bytes
Includes +3 for -n
Give strings on STDIN without final newline
echo -n "Make -> Tissue box" | perl -M5.010 fade.pl

fade.pl:
#!/usr/bin/perl -n
/ -> /;$_=$`^$`^$'^$';{$==rand(y/\x00//)+sleep say+($`&~$_|$'&$_)=~y/\x00/ /r;s%(.*?\K\x00){$=}%\xff%&&redo}

Works as shown, but replace \xhh by the literal characters to get the claimed score.
This way of using \K is new I think...

Awsome, as always! Took me a while to figure out how this works! Nice use of \K indeed. Note that there are two \0 in your code as well as \xff that can  be replace by the corresponding literal characters, so the bytes count is actually 108. Also, maybe you didn't see it, but the input format is free, so there probably is something sorter than -> as a separator.

@Dada Ah right. Thanks. While developing I never use the literal characters, so it's easy to miss things when adjusting the byte count.  Another separator can indeed gain up to 3 bytes, but it's an uninteresting change, so I'll just leave it

Yea of course. I don't recount all your solutions, but only when I experiment on them, and in that case it made me see those 4 bytes that you shouldn't have counted ;)

Python 3, 214 bytes
import time,random
o,f=list(input()),list(input())
F=len(f);O=len(o);o+=[" "]*(F-O);f+=[" "]*(O-F);p=-1;l=[p]
while o!=f:
 while p in l:p=random.randrange(max(F,O))
 l+=[p];o[p]=f[p];print(''.join(o));time.sleep(1)

Ideone it!

Java, 456 454 437 428 bytes
import java.util.*;public class c{public static void main(String[]s)throws Exception{char[]a=s[0].toCharArray(),b=s[1].toCharArray();int l,j=0;if(a.length<b.length){l=b.length;a=Arrays.copyOf(a,l);}else{l=a.length;b=Arrays.copyOf(b,l);}Vector i=new Vector();for(;j<l;i.add(j++));System.out.println(s[0]);while(l>0){Thread.sleep(1000);j=(int)i.remove(new Random().nextInt(l--));a[j]=b[j];System.out.println(String.valueOf(a));}}}

Ungolfed:
import java.util.*;

public class c
{

public static void main(String[] s) throws Exception
{
    char[] a = s[0].toCharArray(), b = s[1].toCharArray();
    int l, j = 0;
    if (a.length < b.length)
    {
        l = b.length;
        a = Arrays.copyOf(a, l);
    }
    else
    {
        l = a.length;
        b = Arrays.copyOf(b, l);
    }

    Vector i = new Vector();

    for (; j < l; i.add(j++));

    System.out.println(s[0]);

    while (l > 0)
    {
        Thread.sleep(1000);
        j = (int) i.remove(new Random().nextInt(l--));
        a[j] = b[j];
        System.out.println(String.valueOf(a));
    }
}
}

Edit: minus 2 byte by  CAD97
Edit: minus 17 byte by Kevin Cruijssen (I slightly altered the suggestion by reusing j instead of creating a new variable x to hold the size)
Edit: minus 9 byte

You have unnecessary whitespace in your two Arrays::copyOf calls

As @CAD97 said, you can remove some unnecessary whitespaces; also at the arrays: String[]s and char[]a. Also, you can golf your first for-loop: for(;j<l;i.add(j++);; You can remove Random r=new Random(); and use it directly: new Random().nextInt(i.size()); You can also add ,x to the list of ints, and chance the while-loop to while((x=i.size())>0){...j=(int)i.remove(new Random().nextInt(x));...} And there is probably more to golf that I'm missing.

PHP, 123 121 bytes
<?=$a=$argv[1];for($b=str_split(str_pad($argv[2],strlen($a)));$b;print"
$a"){$a[$i=array_rand($b)]=$b[$i];unset($b[$i]);}

save as file, execute with php <filename> <string1> <string2> (or php-cgi)
breakdown
<?=$a=$argv[1];                         // 0. print original
for(
    $b=str_split(                       // 2. split to array of single characers
        str_pad($argv[2],strlen($a))    // 1. pad 2nd argument to length of 1st argument
    );
    $b;                                 // 3. while $b has characters left
    print"\n$a"                         // 6. print altered string
){
    $a[$i=array_rand($b)]=$b[$i];       // 4. pick random index from $b, copy character to $a
    unset($b[$i]);                      // 5. remove character from $b
}

CJam, 44 bytes
q~{_,@\Se]s}2*1$peemr{es{_es-zA3#<}g;~t_p}/;

Explanation:
q~                                            get input
  {_,@\Se]s}2*                                pad each string to the length of the other
              1$p                             print starting string
                 eemr{                   }/   for each randomly shuffled enum of target string
                      es{_es-zA3#<}g;         1 second waiting loop
                                     ~t_p     replace one character and print new string
                                           ;  clear stack

The delay only works using the Java interpreter, not in the online interpreter.
 java -jar cjam.jar badfade.cjam <<< '"banana" "republic"'

Try it online (delay set to 1 ms)

JavaScript (ES6) + HTML, 210 bytes
s=>e=>{s=[...s],e=[...e],d=e[k="length"]-s[k],(d>0?s:e).push(..." ".repeat(d>0?d:-d)),a=[...e.keys()],u=_=>{O.value=s.join``,s[i=a.splice(Math.random()*a[k]|0,1)[0]]=e[i],i+1&&setTimeout(u,1e3)},u()}

<input id=O

Called using curry syntax: f("from this")("to this").
Cleaned up JS
s => e => {
    s = [...s],
    e = [...e],
    d = e[ k="length" ] - s[k],
    (d>0 ? s : e).push(..." ".repeat(d>0 ? d : -d)),
    a = [...e.keys()],
    u = _ => {
        O.value = s.join``,
        s[ i = a.splice(Math.random()*a[k]|0, 1)[0] ] = e[i],
        i+1 && setTimeout(u, 1e3)
    },
    u()
}

Test Snippet
Requires closing brace on the input to work here.

f=
s=>e=>{s=[...s],e=[...e],d=e[k="length"]-s[k],(d>0?s:e).push(..." ".repeat(d>0?d:-d)),a=[...e.keys()],u=_=>{O.value=s.join``,s[i=a.splice(Math.random()*a[k]|0,1)[0]]=e[i],i+1&&setTimeout(u,1e3)},u()}

Starting String: <input id="A" type="text">

Ending String: <input id="B" type="text">
<button onclick="f(A.value)(B.value)">Run</button>

<input id=O>

Ruby, 106 bytes
->a,b{puts a=a.ljust(l=[a.size,b.size].max);b=b.ljust l
[*0...l].shuffle.map{|i|sleep 1;a[i]=b[i];puts a}}

Try it online!
Oh, all right. No more rick rolling in the Try It Online link, if that's what's causing the downvotes. If not, please let me know what I'm doing wrong