The highest prime factor of neighboring numbers

Question

I think it's easiest to explain this challenge in a sequential manner. Start with an input number N and:

1. Find its highest prime factor
2. Check numbers above and below N and see if the highest prime factor is higher (i.e. the highest prime factor of N-1 and/or N+1 is higher than the factor of N.
3. Continue to check higher and/or lower numbers neighboring N in the directions where the highest factors are increasing ((N-2, N-3 ...) and/or (N+2, N+3 ...) and so on)
4. Once there aren't any prime factors in either direction that are higher than the ones we've already found we stop and output the highest prime factor we have encountered.

Let's look at an example:

245 has the prime factors 5, 7, 7. Its neighbors are:

244 -> 2,  2,  61
245 -> 5,  7,  7
246 -> 2,  3,  41

The highest prime factor is increasing in both direction, so we must look at the next neighbor:

243 -> 3,   3,  3,  3,  3
244 -> 2,   2,  2,  61
245 -> 5,   7,  7
246 -> 2,   3,  41
247 -> 13,  19

The highest prime factors are now decreasing in both direction, so the highest prime factor we've encountered is 61, and should therefore be returned.

Another example:

Let's look at 1024. Its prime factors are 2, 2, 2, 2, 2, 2, 2, 2, 2, 2. The prime factors of its nearest neighbors are:

1023 -> 3, 11, 31
1024 -> 2,  2,  2,  2,  2,  2,  2,  2,  2,  2
1025 -> 5,  5, 41

The highest prime factor are increasing in both direction, from 2 to 31 or 41. Let's look at the neighbors:

1022 -> 2, 7,  73
1023 -> 3, 11, 31
1024 -> 2,  2,  2,  2,  2,  2,  2,  2,  2,  2
1025 -> 5,  5, 41
1026 -> 2,  3,  3, 19

The highest prime factor for 1022 is 73, and the highest prime factor for 1026 is 19. Since 19 is lower than 41 we're not interested in it. It's still increasing for numbers smaller than N, so we'll check the next one in that direction:

1021 -> 1021
1022 -> 2, 7,  73
1023 -> 3, 11, 31
1024 -> 2,  2,  2,  2,  2,  2,  2,  2,  2,  2
1025 -> 5,  5, 41
1026 -> 2,  3,  3, 19

1021 is a prime, and the highest prime we've encountered, so it should be returned.

Rules:

• You will only get positive N larger than 1 and smaller than 2^31-2.
• Input and output formats are optional, but the numbers must be in base 10.
• You should continue searching for higher primes as long as the highest value is increasing in that direction. The directions are independent of each other.

Test cases:

Format: N, highest_factor

2, 3
3, 3
6, 7
8, 11
24, 23 
1000, 997
736709, 5417 
8469038, 9431

Answer 1

Mathematica, 82 74 bytes

Thanks to Martin Ender for saving 8 bytes!

Max@@(±n_:=#//.x_/;l[t=x+n]>l@x:>t;l=FactorInteger[#][[-1,1]]&)/@{±-1,±1}&

Unnamed function taking an integer input and returning an integer.

±n_:=#//.x_/;l[t=x+n]>l@x:>t defines a unary function ± which keeps increasing the global function's integer input by n as long as the largest prime factor is increasing. (The largest-prime-factor function is defined with l=FactorInteger[#][[-1,1]]&.) {±-1,±1} therefore applies that function twice to the input integer, with increment -1 and again with increment 1. Then, Max@@(...l...)/@... takes the larger of the two largest-prime-factors thus found.

Previous submission:

Max@@(l=FactorInteger[#][[-1,1]]&)/@(#//.x_/;l[t=x+#2]>l[x]:>t&@@@{{#,-1},{#,1}})&

Answer 2

Perl, 137 bytes

122 bytes of code + 15 bytes for -p and -Mntheory=:all.

sub f{$t=(factor$_+pop)[-1]}$i=$j=1;while($i|$j){f++$c;($i&=$t>$h)&&($h=$t);f-$c;($j&=$t>$l)&&($l=$t)}$_=$h>$l?$h:$l?$l:$_

To run it:

perl -pMntheory=:all -e 'sub f{$t=(factor$_+pop)[-1]}$i=$j=1;while($i|$j){f++$c;($i&=$t>$h)&&($h=$t);f-$c;($j&=$t>$l)&&($l=$t)}$_=$h>$l?$h:$l?$l:$_' <<< 736709

If you don't have ntheory installed, you can install it by typing (echo y;echo) | perl -MCPAN -e 'install ntheory' in your terminal.

Answer 3

Ruby, 99 bytes

->n{f=->n{i=2;n%i<1?n/=i:i+=1while i<n;n};g=->s,z{s+=z while f[s+z]>b=f[s];b};[g[n,1],g[n,-1]].max}

Explanation:

• f() is the highest prime factor
• g() is the function searching neighbors in one direction
• apply g to (n,-1) and to (n,+1) to search in both directions