# The highest prime factor of neighboring numbers

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

• Let's say we get a highest prime factor of2 for N. We then get 5 for N-1 and 61 for N+1. Then we get 19 for N-2 and 67 for N+2. Should we keep trying lower numbers, since 19>5 or stop, since 5<61? I.e. are the maxima kept per-side? (I'm not sure if the example is mathematically possible.) Jan 16, 2017 at 8:33
• @Pietu1998, is the question more clear now? Jan 16, 2017 at 16:07
• N=2 actually seems to be an edge case since 1 has no prime factors, so no maximum prime factor with which we may compare in order to decide whether we should continue. Jan 16, 2017 at 20:15

# 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}})&

• Saved a few bytes by avoiding the @@@ (and you can use l@x there): Max@@(±n_:=#//.x_/;l[t=x+n]>l@x:>t;l=FactorInteger[#][[-1,1]]&)/@{±-1,±1}& Jan 16, 2017 at 8:08

## 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.

## 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

# Jelly, 24 bytes

;‘ÆfṀ€>/
ÇÐḟṖ‘,Ç1#Ṫ€ÆfFṀ


Try it online!

Bleh

## How it works

;‘ÆfṀ€>/ - Helper link. Takes n on the left
‘       - Yield n+1
;        - Pair; [n, n+1]
Æf     - Prime factors of each
Ṁ€   - Maximum of each
>/ - Is max(pf(n)) > max(pf(n+1))?

ÇÐḟṖ‘,Ç1#Ṫ€ÆfFṀ - Main link. Takes N on the left
ÇÐḟ             - Remove all integers 1 ≤ k ≤ N which return true under the helper link
Ṗ            - Remove the last one (N)
‘           - Increment all
Ç1#       - Find the first integer ≥ N which the helper link returns true
,          - Pair
Ṫ€     - Get the last element of each
This returns [x, y] where
x is the lower neighbour with the highest prime factor,
y is the upper neighbour with the highest prime factor
Æf   - Prime factors of each
FṀ - Flatten and get the maximum