A196941 a(n) is the minimum prime (or 1) needed to write integer n into the form n = a + b such that all prime factors of a and b are smaller or equal to a(n).

1, 2, 2, 2, 2, 3, 2, 2, 2, 3, 2, 3, 3, 3, 2, 2, 2, 3, 2, 3, 3, 5, 2, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 3, 2, 3, 3, 3, 2, 3, 3, 3, 3, 3, 5, 5, 2, 3, 3, 3, 3, 5, 3, 3, 3, 3, 3, 3, 3, 5, 3, 3, 2, 2, 2, 3, 2, 5, 3, 7, 2, 3, 3, 3, 3, 5, 3, 5, 2, 3, 3, 3, 3, 3, 3, 3, 3

Offset: 2

Author

Lei Zhou, Oct 07 2011

Keywords

• nonn
• easy

Comments

Any integer n that is greater than 1 can be written into the sum of two other positive integers, such that n = a + b. There are IntegerPart[n / 2] ways to do this assuming a <= b. For each of the ways, we can have a set of prime factor of a and b, defined as sa = FactorSet[a] and sb = FactorSet[b], quoting the function in the Mathematica program. Then we can define a union set s=Union[sa, sb], which is a list of prime factors that can factor either a or b. In this way we obtain IntegerPart[n / 2] of possible set s. Define p_i is the largest prime number in each of set s_i, i = 1,2...IntegerPart[n / 2], a(n) = the smallest s_i.

Though 2 = 1 + 1 and 1 is not a prime number, a(2) can still be defined as 1.

The Mathematica program generates up to term 88.

The first occurrence of a(n)=k forms sequence A000229. - Lei Zhou, Feb 06 2014

Examples

			n = 3, 3 = 1 + 2, the largest prime factor of 1 and 2 is 2, so a[3] = 2;
n = 4, 4 = 2 + 2, the largest prime factor of 2 and 2 is 2, so a[4] = 2;
[in 4 = 1 + 3, the largest prime factor of 1 and 3 is 3, which is larger than a[4] = 2]
...
n = 23, 23 = 3 + 20 = 3 + 2^2 * 5, the largest prime factor of 3 and 20 is 5, so a[23] = 5;
		

Links

• T. D. Noe, Table of n, a(n) for n = 2..10000

Crossrefs

Cf. A173786 (n for which a(n)=2), A196526, A000229.

Programs

Mathematica

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]; Table[min = n; Do[r = n - k; s = Union[FactorSet[k], FactorSet[r]]; If[a = s[[Length[s]]]; a < min, min = a], {k, 1, IntegerPart[n/2]}]; min, {n, 2, 88}]
LPF[n_] := FactorInteger[n][[-1,1]]; Table[Min[Table[Max[{LPF[i], LPF[n-i]}], {i, Floor[n/2]}]], {n, 2, 100}] (* T. D. Noe, Oct 07 2011 *)