* Allan Wechsler <acwacw@gmail.com> [Nov 18. 2012 18:21]:
At least for the first few positive n, the factorization of 1 + n + n^2 contains a prime larger than n. The first counterexample is at n=16; here 1 + n + n^2 = 273 = 3*7*13.
I've only explored the question by hand, but so far I've found no counterexamples for the special case when n is prime. Can somebody with a few free minutes find one?
[...]
Some pairs [n,p] where p is the largest prime (and p<n): (Pari/GP code): ? for(n=1,10^3,f=factor(n^2+n+1);f=f[,1];p=f[#f];if(p<n,print1([n,p],", "));); [16, 13], [18, 7], [22, 13], [30, 19], [49, 43], [67, 31], [68, 19], [74, 61], [79, 43], [81, 73], [87, 31], [100, 37], [102, 79], [121, 37], [135, 61], [137, 73], [146, 127], [149, 103], [154, 109], [158, 97], [159, 103], [163, 67], [165, 43], [169, 157], [172, 109], [178, 43], [181, 139], [191, 31], [211, 37], [221, 163], [229, 181], [230, 67], [235, 139], [256, 241], [262, 223], [263, 109], [269, 151], [273, 127], [277, 193], [291, 199], [292, 79], [301, 193], [305, 199], [313, 181], [315, 31], [324, 307], [326, 157], [334, 151], [352, 97], [361, 127], [372, 109], [373, 73], [380, 43], [393, 277], [406, 223], [410, 181], [423, 97], [429, 73], [430, 379], [431, 397], [436, 211], [439, 67], [450, 367], [458, 157], [459, 139], [466, 241], [470, 193], [471, 349], [484, 463], [485, 223], [490, 199], [494, 193], [497, 241], [499, 109], [501, 61], [513, 271], [520, 97], [521, 283], [527, 313], [529, 79], [552, 229], [562, 61], [565, 67], [571, 151], [575, 349], [581, 37], [583, 523], [590, 457], [592, 229], [596, 307], [608, 109], [610, 439], [615, 157], [618, 211], [625, 601], [631, 433], [638, 499], [640, 157], [653, 19], [655, 79], [657, 373], [667, 433], [670, 541], [674, 631], [676, 37], [687, 193], [699, 109], [706, 439], [707, 241], [710, 163], [714, 277], [718, 61], [724, 313], [737, 139], [738, 241], [766, 79], [767, 103], [772, 181], [780, 457], [781, 229], [784, 757], [787, 151], [790, 577], [802, 337], [809, 379], [811, 97], [817, 607], [820, 643], [821, 421], [823, 751], [828, 397], [840, 313], [841, 271], [856, 193], [858, 499], [862, 421], [867, 73], [871, 619], [873, 163], [880, 193], [893, 283], [900, 67], [904, 463], [908, 127], [919, 163], [924, 349], [928, 673], [935, 109], [938, 307], [940, 577], [947, 463], [952, 541], [954, 829], [957, 661], [961, 331], [971, 919], [985, 619], [991, 277], [997, 823],