A327466 Number of nonempty subsets of [1..n] which are geometric progressions with rational ratio and are locally maximal.

1, 1, 3, 4, 8, 13, 19, 23, 27, 36, 46, 55, 67, 80, 94, 103, 119, 132, 150, 167, 187, 208, 230, 250, 266, 291, 311, 336, 364, 393, 423, 447, 479, 512, 546

Offset: 1

Author

N. J. A. Sloane, Sep 29 2019

Keywords

• nonn
• more

Comments

"Locally maximal" subsets are those subsets in geometrical progression that cannot be extended to a larger subset of [1..n] in geometric progression. [Comment made precise by Giovanni Resta, Sep 30 2019.]

One might have expected that the GP would be required to have an integer ratio, but in fact we allow rational ratios. The GPs can be assumed to be strictly increasing. - N. J. A. Sloane, Oct 03 2019

Examples

			Illustrations of some initial terms:
n=3: (12),(13),(23).
n=4: (124),(13),(23),(34).
n=8: (1248), plus all 28 pairs (ij) from [1..8] except the six subsets of (1248), so a(8) = 1 + 28 - 6 = 23.
		

Crossrefs

See A327469 for GPs of length > 2.

Cf. A309095.

Programs

Mathematica

a[1] = 1; a[n_] := Block[{t = Select[ Subsets[ Range[n], {2, Ceiling[ Log2[n + 1]]}], Length@ Union[ Rest[#]/ Most[#]] == 1 &], i = 2}, t = Reverse@ SortBy[t, Length]; i=2; While[i <= Length[t], If[ AnyTrue[ Take[t, i-1], SubsetQ[#, t[[i]]] &], t = Delete[t, i]; i=2; Continue[], i++]]; Length@ t]; Array[a, 16] (* Giovanni Resta, Sep 30 2019 *)

Extensions

a(9)-a(35) from Giovanni Resta, Sep 30 2019