Return to Answer

Another implementation using NestWhile:

f[p_]:=NestWhile[2 # &, 2^Ceiling[Log[2, p]], !PrimeQ[# - p] &] - p; f[857] f[859] (*167*) (*7333*) 

Another implementation using NestWhile:

f[p_]:=NestWhile[2 # &, 2^Ceiling[Log[2, p]], !PrimeQ[# - p] &] - p; f[857] f[859] (*167*) (*7333*) 

Some primes have crazy large values:

plotData = Table[{i, f[i]}, {i, Prime[Range[285]]}]; ListLinePlot[plotData, PlotRange -> All, ScalingFunctions -> "Log"] 

In fact, some are so large I haven't even gotten an answer: f[1871] just runs indefinitely.

Another implementation using NestWhile:

f[p_]:=NestWhile[2 # &, 2^Ceiling[Log[2, p]], ! PrimeQ[# - p] &] - p; f[857] f[859] (*167*) (*7333*) 

Add-on: Unrelated, but I just had to add this plot also because it looks very interesting

ListLinePlot[f[Prime[Range[10000]]], Joined -> True] 

Another implementation using NestWhile:

f[p_]:=NestWhile[2 # &, 2^Ceiling[Log[2, p]], !PrimeQ[# - p] &] - p; f[857] f[859] (*167*) (*7333*) 

Another implementation using NestWhile:

f[p_]:=NestWhile[2 # &, 2^Ceiling[Log[2, p]], CompositeQ[# - p] &] - p; f[857] f[859] (*167*) (*7333*) 

Add-on: Unrelated, but I just had to add this plot also because it looks very interesting

ListLinePlot[f[Prime[Range[10000]]], Joined -> True] 

Another implementation using NestWhile:

f[p_]:=NestWhile[2 # &, 2^Ceiling[Log[2, p]], ! PrimeQ[# - p] &] - p; f[857] f[859] (*167*) (*7333*) 

Add-on: Unrelated, but I just had to add this plot also because it looks very interesting

ListLinePlot[f[Prime[Range[10000]]], Joined -> True]