cp's OEIS Frontend

A026477 a(1) = 1, a(2) = 2, a(3) = 3; and for n > 3, a(n) = smallest number > a(n-1) and not of the form a(i)*a(j)*a(k) for 1 <= i < j < k < n.

%I A026477 #43 Aug 05 2024 22:02:45
%S A026477 1,2,3,4,5,7,9,11,13,16,17,19,23,25,29,31,37,41,43,47,49,53,59,61,67,
%T A026477 71,73,79,81,83,89,97,101,103,107,109,113,120,121,127,131,137,139,149,
%U A026477 151,157,163,167,168,169,173,179,181,191,193,197,199,210,211,216,223
%N A026477 a(1) = 1, a(2) = 2, a(3) = 3; and for n > 3, a(n) = smallest number > a(n-1) and not of the form a(i)*a(j)*a(k) for 1 <= i < j < k < n.
%C A026477 From _Bob Selcoe_, Aug 25 2016: (Start)
%C A026477 Once a term with a given prime signature S (i.e., multiset of prime exponents) appears, then all numbers with the same prime signature follow. So either all or no terms with the same prime signature appear (first conjectured by _Charles R Greathouse IV_).
%C A026477 Proof:
%C A026477 i. Let S = {i,j,k..,y}, i>=j>=k.. be prime signatures, i.e., numbers of the form (p^i*q^j*r^k..*z^y) where {p,q,r,..,z} are distinct primes; denote S = {} as the signature for p^0 = 1.
%C A026477 ii. By definition, 1 and all primes p appear in the sequence; so terms where S = {k} (i.e., one-digit signatures denoting prime powers p^k) are k=0 and k = A026474(n) = {1,2,4,8,15,22,29..}, because k cannot be the sum of any combination of 3 smaller k. So the only prime power terms are p^0 = 1 and p^A026474(n), or S = {}, {1}, {2}, {4}, {8}, {15}, {22}, {29}...
%C A026477 iii. By induction, once S = {k} is determined, all other terms with the same prime signature appear (or do not) depending on the various combinations of signature exponents of previous terms with smaller signature sums. So for example, terms with the same two-digit signature S = {k,k} (i.e. (pq)^k) are constrained by the following: since p = {1} and q = {1} appear, then (pq) = {1,1} does not because in this case {1}*{1}*{} = {1,1}; since p^2 = {2} and q^2 = {2} appear, then (pq)^2 = {2,2} does not; since {4} appears but {3} does not, then {3,3} appears but {4,4} and {5,5} do not (the latter because {3,3}*{2}*{2} = {5,5} when p^2,q^2 = {2}). Note that {3,3} would not appear if {3,2} appeared because {3,2}*{1}*{} = {3,3} when q = {1}; but because p = {1} and p^2,q^2 = {2} appear, then {2}*{2}*{1} = {3,2} does not. {6,6} does not appear because {6,5} appears (by virtue of other constraints) and {6,5}*{1}*{} = {6,6} when q = {1}. Determining which signatures appear and which do not becomes increasingly complicated as the sequence increases.
%C A026477 _Don Reble_ offered a proof on the Sequence Fans Mailing List which seems to be different (and certainly more formal) than mine. Perhaps mine is more of an "explanation" than a "proof"? (End)
%H A026477 Charles R Greathouse IV, <a href="/A026477/b026477.txt">Table of n, a(n) for n = 1..10000</a>
%t A026477 a = {1, 2, 3}; no = {1 2 3};
%t A026477 Do[x = SelectFirst[Range[Last[a] + 1, 1000], ! MemberQ[no, #] &]; AppendTo[a, x]; no = Union[Times @@@ Subsets[a, {3}]], 200]; a (* _Robert Price_, May 26 2019 *)
%o A026477 (PARI) list(lim)=my(v=List(),n,d,k); while(n++<=lim, d=divisors(n); for(i=1,#d-2, if(!setsearch(v,d[i]), next); for(j=i+1,#d-1, if(!setsearch(v,d[j]), next); k=n/(d[i]*d[j]); if(d[j]>=k, break); if(denominator(k)==1 && setsearch(v,k), next(3)))); listput(v,n)); Vec(v) \\ _Charles R Greathouse IV_, Sep 16 2015
%Y A026477 Cf. A000028, A026416, A066724, A050376, A084400, A026474.
%Y A026477 There are six related sequences: A026477: 1 <= i <  j <  k < n  starting 1,2,3; A026478: 1 <= i <= j <= k < n  starting 1,2,3; A026479: 1 <= i <  j <  k < n  starting 1,2,4; A026480: 1 <= i <= j <= k < n  starting 1,2,4; A026481: 1 <= i <  j <  k < n  starting 1,3,4; A026482: 1 <= i <= j <= k < n  starting 1,3,4.
%K A026477 nonn
%O A026477 1,2
%A A026477 _Clark Kimberling_
%E A026477 More terms from _Christian G. Bower_, Nov 15 1999