A074885 Numbers not of the form x^2 + M*y^2 for integers x > 0, y > 1, M > 0.

1, 2, 3, 4, 6, 7, 11, 14, 15, 23, 30, 35, 38, 39, 42, 47, 62, 71, 78, 83, 87, 95, 110, 119, 138, 143, 155, 158, 167, 182, 195, 203, 210, 215, 222, 227, 230, 255, 263, 282, 287, 302, 318, 327, 335, 383, 390, 395, 398, 435, 447, 455, 462, 483, 503

Offset: 1

Author

Chris Boyd and Robert G. Wilson v, Sep 12 2002

Keywords

• nonn
• nice

Comments

"... 730847, 911027, 1011218, 1122558, 1153547, 1191302, 1195862, 1198823, 1200023, 1215843, 1230990, 1586343, 1607627, 1875902. There is strong numerical evidence that the series ends at 1875902. I calculate that the series has 436 members <= 1875902. 1875902 looks like the largest natural number n with this property (I have checked up to 100,000,000). If true, every sufficiently large number is expressible as x^2 + M*y^2 with x > 0, y > 1, M > 0, or (prosaically) as the sum of a square (A000290) and a not squarefree number (A013929)." - Chris Boyd (and modified by Robert G. Wilson v, Sep 30 2012)

Number of terms less than or equal to 10^k, k=1...7: 6, 22, 81, 210, 367, 424, 436.

Least number of the form x^2 + m*y^2 in k different ways, k=0...: 1, 5, 21, 13, 25, 37, 41, 68, 52, 81, 73, 100, 97, 160, 169, 148, 145, 153, 193, 261, 288, ..., . - Robert G. Wilson v, Sep 30 2012

References

• Postings to sci.math Aug 24 2002, 03:04PM and Aug 26 2002, 03:07PM by Chris Boyd

Links

• T. D. Noe, Table of n, a(n) for n = 1..436 (probably complete)
• Eric Weisstein's World of Mathematics, Pell Equation.

Programs

Mathematica

notOfTheFormQ[n_] := Do[r = Reduce[x >= 1 && y > 1 && x^2 + m*y^2 == n, {x, y}, Integers]; If[r =!= False, Return[True]], {m, 1, Ceiling[(n - 1)/4]}] =!= True; Reap[ Do[ If[ notOfTheFormQ[n], Print[n]; Sow[n]], {n, 1, 600}]][[2, 1]] (* Jean-François Alcover, Sep 28 2012 *)
fQ[n_] := Block[{flg = 0, lmt = 1 + Floor@ Sqrt@ n, m, x, y = 2}, While[y < lmt && flg == 0, x = 1; While[m = Floor[(n - x^2)/y^2]; m > 0 && Mod[n - x^2, y^2] != 0, x++]; If[n == x^2 + m*y^2, flg = 1]; y++]; flg == 0]; Select[Range@509, fQ] (* much faster than the above, Robert G. Wilson v, Sep 29 2012 *)
mx = 1000; cnt = Table[0, {mx}]; Do[q = x^2 + m*y^2; If[q <= mx, cnt[[q]]++], {m, (mx - 1)/4}, {x, Sqrt[mx - 4 m]}, {y, 2, Sqrt[(mx - x^2)/m]}]; Flatten[Position[cnt, 0]] (* T. D. Noe, Sep 28 2012 *)

PARI

isOK(n) = my(k=1); while(k*kColin Barker, Apr 26 2014

Perl

$xleast=1; $yleast=2; $start=1; $range=2000000; $xprev=$xleast-1; for ($k=0; ($k+$yleast)*($k+$yleast) <= $start+$range; $k++ ) { $asquares[$k]=($k+$yleast)*($k+$yleast); } for ($k=$start; $k<$start+$range; $k++ ) {&donum; } sub donum { $nm=$k-$xprev*$xprev; for ($i=$xprev; $i<=$nm; $i++ ) {if ( ($nm -= $i+$i+1) < 0 ) { last; } if (&ncheck($nm) > 0) { return; } } printf("%d\n", $k); } sub ncheck { $j=0; while ( ($sq = $asquares[$j++ ]) <= $[0] ) { if ($[0] % $sq == 0) { return 1; } } return 0;}