A196526 -id:A196526 - cp's OEIS frontend

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

Lei Zhou, Oct 07 2011

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

			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;

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

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

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 *)

A195061 a(n) is the minimum numbers of ks in the sum of a=b_k+c_k, b_k is positive even number and c_k is odd number greater than or equal to -1, and b and c has only prime factors smaller than sqrt(prime(n)), such that the prime factors of all b_k and c_k contain every primes that is smaller than the square root of n-th prime.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2

Offset: 2

Lei Zhou, Oct 03 2011

From A196526, every prime number can be written into at least one ways in the form p=b+c, while b is a positive even number, and c is an odd number that is -1 or greater, and all prime factors of b and c are smaller than square root of the n-th prime or equal to 2.
Defining the set of 2 and all primes that are smaller than square root prime(n) as set PP.
In principle any pair of b and corresponding c=p-b are coprimes.
For each pair of b and c in the set of SS={{b1,c1},{b2,c2},...,{bk,ck}}, if we make a set s_k that lists all prime factors (no repetition) of bk and ck, s_k will be a subset of the set PP.
Then we can pick up a few elements of set SS, say {b_s1,cs1},{b_s2,c_s2}...{b_sm,c_sm}, such that the union of prime factor set s_s1, s_s1...s_sm, define as set TT, will be equal to the set PP.
a(n) is the minimum needed number of element m, such that the prime factors of the b and c in these picked elements will traverse all element of set PP.

			for n=2, prime(2)=3, 3=2+1, PP={2}, b=2, c=1, TT={2}=PP, so a(2)=1;
for n=3, prime(3)=5, 5=2^2+1, PP={2}, b=2^2, c=1, TT={2}=PP, so a(3)=1;
...
for n=37, prime(37)=157, 157=2*5+3*7^2=2*11+3^3*5, PP={2,3,5,7,11}, b1=2*5, c1=3*7^2; b2=2*11, c2=3^3*5; TT={2,3,5,7,11}=PP, so a{37}=2

Cf. A196526.

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];
Checkk[k_, n_] :=
Module[{allp, checkp, fsp, alls, subs, esubs, lsub, found, i, j},
  allp = AllPrimes[n]; alls = AllSplits[n]; subs = Subsets[alls, {k}];
   lsub = Length[subs]; i = 0; found = 0;
  While[(found == 0) && (i < lsub), i++; esubs = subs[[i]];
   checkp = {};
   Do[fsp = FactorSet[esubs[[j]][[2]]]; checkp = Union[checkp, fsp];
    If[Abs[esubs[[j]][[3]]] != 1, fsp = FactorSet[esubs[[j]][[3]]];
     checkp = Union[checkp, fsp]], {j, 1, k}];
   If[Length[checkp] == Length[allp], found = 1]]; found];
Checks[n_] :=
Module[{found, i}, found = 0; i = 0;
  While[found == 0, i++; found = Checkk[i, n]]; i]; Table[
Checks[i], {i, 2, 100}]

A196558 a(n) is the index of the first occurrence of n in A195061.

Original entry on oeis.org

2, 36, 108, 284

Offset: 1

Lei Zhou, Oct 03 2011

In sequence A195061, the 2nd through 25th terms are 1's, which means it is possible to find a sum of p=b+c, p=prime(n), the prime factors of b and c traverse all primes smaller than sqrt(prime(n)). From the 36th term, the above case no longer holds for most primes. However, if you choose two eligible sums p=b1+c1=b2+c2, it becomes possible that the union set of prime factors of b1, c1, b2, and c2 traverses all primes smaller than sqrt(prime(n)). This stands until prime(107)=587. For prime(108)=593, no group of two b's and c's can have the union set of their prime factors to traverse all primes smaller than sqrt(prime(n)). Three groups of b's and c's will be needed to do so. And starting from prime(284)=1861, four groups are needed for some of the numbers.

The listed Mathematica program fails to find a(5) since it exceeds the integer range as index.

			A195061(2)=1 => a(1)=2;
A195061(3)=A195061(4)=...=A195061(35)=1; A195061(36) = 2 => a(2)=36;
A195061(1..107) <= 2; A195061(108)=3 => a(3)=108;
A195061(1..283) <= 3; A195061(284)=4 => a(4)=284.

Cf. A196526, A195061.

(* Taking the function Checks[n_] in the Mathematica program for A195061, the following program gives the first four terms: *)
k = 0; i = 1; a = 0;
Array[ff, 4];
Do[ff[j] = 0, {j, 1, 4}]; While[(k < 4) && (a < 4), i++; a = Checks[i]; If[(a <= 4) && (ff[a] == 0), ff[a] = i;k++]];
Table[ff[m], {m, 4}]

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A196558 a(n) is the index of the first occurrence of n in A195061.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica