A196526 a(n) is the number of ways the n-th prime number prime(n) can be written as sum of coprime b and c, in which b is a positive even number and c is an odd number that is -1 or greater, and all odd prime factors of b and c are less than or equal to sqrt(prime(n)).

2, 1, 1, 3, 2, 3, 2, 1, 5, 5, 4, 4, 3, 4, 8, 8, 7, 7, 7, 7, 8, 7, 8, 7, 6, 6, 7, 7, 7, 12, 13, 12, 11, 12, 10, 10, 11, 11, 16, 18, 18, 18, 17, 18, 18, 17, 16, 15, 16, 17, 15, 18, 18, 18, 18, 17, 16, 18, 17, 16, 24, 24, 23, 23, 23, 23, 24, 23, 24, 24, 25, 32, 33, 34, 33, 36, 34, 35, 33, 35, 33, 32, 35, 34, 33, 33, 34, 33, 35, 34, 31, 32, 30, 35, 35, 34, 32, 32, 45

Offset: 2

Author

Lei Zhou, Oct 03 2011

Keywords

• nonn
• easy

Comments

All terms are positive integers, no zero term.

The Mathematica program generates first 99 items and the function AllSplits[n_] can be used to generate a(n) for any n > 1.

Examples

			n=2: prime(2)=3 = 2 + 1 = 2^2 - 1, so a(2)=2;
n=3: prime(3)=5 = 2^2 + 1, so a(3)=1;
...
n=10: prime(10)=29, int(sqrt(29))=5, 29 = 2+3^3 = 2^2+5^2 = 2^2*5+3^2 = 2^3*3+5 = 2*3*5-1, so a(10)=5.
		

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 2..1000

Crossrefs

Cf. A006530 (largest prime factor), A000040.

Programs

Haskell

a196526 n = length [c | let p = a000040 n,
                        c <- [-1,1..p-1], let b = p - c,
                        gcd b c == 1,
                        a006530 b ^ 2 < p || p == 3, a006530 c ^ 2 < p]
-- Reinhard Zumkeller, Oct 04 2001

Mathematica

AllPrimes[k_] :=
Module[{p, maxfactor, pset}, p = Prime[k];
  maxfactor = NextPrime[IntegerPart[Sqrt[p]] + 1, -1];
  If[maxfactor == -2, pset = {2}, p0 = 2; pset = {2};
   While[p0 = NextPrime[p0]; p0 <= maxfactor,
    pset = Union[pset, {p0}]]]; pset];
NextIntegerWithFactor[seed_, fset_] :=
Module[{m, a, l, i, fset1}, m = seed - 1;
  While[m++; If[Mod[m, 2] == 1, m++]; a = FactorInteger[m];
   l = Length[a]; fset1 = {};
   Do[fset1 = Union[fset1, {a[[i]][[1]]}], {i, 1, l}];
   Intersection[fset1, fset] != fset1]; m];
FactorSet[seed_] :=
Module[{fset2, a, l, i}, a = FactorInteger[seed]; l = Length[a];
  fset2 = {}; Do[fset2 = Union[fset2, {a[[i]][[1]]}], {i, 1, l}];
  fset2]; SplitPrime[n_, q0_] :=
Module[{p, pset, q, r, rp, fs, rs, qs}, p = Prime[n];
  pset = AllPrimes[n]; q = q0;
  While[q++; q = NextIntegerWithFactor[q, pset]; r = p - q;
   rp = Abs[r]; fs = FactorSet[rp];
   rs = Complement[pset, FactorSet[q]];
   qs = Intersection[fs,
     rs]; (fs != {1}) && (fs != qs) && (q <= (p + 1))]; {p, q, r} ];
AllSplits[n_] :=
Module[{q, ss, spls}, q = 0; spls = {};
  While[ss = SplitPrime[n, q]; q = ss[[2]];
   If[q <= (Prime[n] + 1), spls = Union[spls, {ss}]];
   q < (Prime[n] + 1)]; spls]; Table[
Length[AllSplits[i]], {i, 2, 100}] (* Lei Zhou *)
zhouAbleCount[n_] := Length[Select[Range[-1, Prime[n], 2], GCD[#, Prime[n] - #] == 1 && FactorInteger[#][[-1, 1]] <= Sqrt[Prime[n]] && (IntegerQ[Log[2, Prime[n] - #]] || FactorInteger[Prime[n] - #][[-1, 1]] <= Sqrt[Prime[n]]) &]]; Table[zhouAbleCount[n], {n, 2, 100}] (* Alonso del Arte, Oct 03 2011 *)