[seqfan] Re: Smallest number not of the form a(i)*a(j)*a(k) for 1 <= i < j < k < n

[David Wilson]

> -----Original Message-----
> From: SeqFan [mailto:seqfan-bounces at list.seqfan.eu] On Behalf Of Charles
> Greathouse
> Sent: Wednesday, September 16, 2015 11:00 PM
> To: Sequence Fanatics Discussion list
> Subject: [seqfan] Smallest number not of the form a(i)*a(j)*a(k) for 1 <= i < j
> < k < n
> 
> Sequence A026477 is defined as:
> 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.
> 
> It seems that there should be a succinct description for this sequence in
> terms of the exponents appearing in the prime factorization of n (such as
> there is for A026422). Can any prove or disprove this claim?

I am fairly certain that you could prove that if two numbers have the same prime signature (multiset of exponents in its prime factorization) then they are either both in or both out of A026422. I believe you could fashion an inductive proof showing that if all numbers N with Omega(n) = A001222(n) < n have the property, then so do all numbers with Omega(n+1) = n. The base case for numbers with Omega(n) = 0 is trivial, since the only such number is n = 1.

This would establish that the membership of n in  A026477 is determined by the prime signature of n, I think this is indeed the case. I checked that this is the case for n <= 10000. Here are a few small prime signatures for elements of A026477:

() (1) (2) (4) (3,1,1) (1,1,1,1) (3,3) (8) (7,1) (6,2,1) (2,2,2,1) (5,2,2) (10,1,1) (6,5) (8,1,1,1) (10,3) (15) (14,1) (13,2) (3,3,1,1,1) (3,1,1,1,1,1)

I don't see any succinct pattern in these prime signatures, your mileage may vary.

As you mentioned, the prime powers in A026477 are 1 and any p^A026422(k).
The squarefrees in A026477 are 1 and any product of A016777(k) distinct primes.

> It's clear that every prime appears, as does every square of a prime, but that
> no cubes of primes can appear. By induction p^e appears with e in (0, 1, 2, 4,
> 8, 15, 22, 29, ...) =~ A026474, a linear recurrence.
> 
> Charles Greathouse
> Analyst/Programmer
> Case Western Reserve University
> 
> _______________________________________________
> 
> Seqfan Mailing list - http://list.seqfan.eu/