A394865 a(n) is the size of the largest subset A of {1, ..., n} such that x does not divide 2*y for each pair of distinct elements x, y in A.

1, 1, 1, 2, 3, 3, 4, 4, 4, 4, 5, 5, 6, 6, 6, 7, 8, 8, 9, 10, 10, 10, 11, 11, 12, 12, 12, 13, 14, 14, 15, 15, 15, 15, 16, 16, 17, 17, 17, 17, 18, 18, 19, 20, 20, 20, 21, 21, 22, 22, 22, 23, 24, 24, 25, 25, 25, 25, 26, 26, 27, 27, 27, 28, 29, 29, 30, 31, 31, 31

Offset

1,4

Comments

a(n) is the number of terms of A084087 not exceeding n.

The construction of the largest subset is to choose all numbers n/3 < m <= n such that the 2-valuation of m is even.

Links

Paolo Xausa, Table of n, a(n) for n = 1..10000

Formula

Limit_{n->oo} a(n)/n = 4/9.

a(n) = A050292(n) - A050292(floor(n/3)). - David Radcliffe, Jun 13 2026

Example

For n = 7, the largest such subset is {3, 4, 5, 7}, so a(7) = 4.

Mathematica

A050292[n_] := A050292[n] = If[n == 0, 0, n - A050292[Quotient[n, 2]]];
A394865[n_] := A050292[n] - A050292[Quotient[n, 3]];
Array[A394865, 100] (* Paolo Xausa, Jun 17 2026 *)
(* Alternative: *)
Accumulate[Array[Boole[!Divisible[#, 3] && EvenQ[IntegerExponent[#, 2]]] &, 100]] (* Paolo Xausa, Jun 17 2026 *)

Prog

(PARI) lista(nn) = {my(cnt = 0); for(n = 1, nn, if(gcd(n, 3) == 1 && valuation(n, 2) % 2 == 0, cnt++); if(n > 1, print1(", ")); print1(cnt); ); }

Crossrefs

Cf. A050292, A084087.

Sequence in context: A061775 A356384 A385900 * A225634 A247134 A080604

Adjacent sequences: A394862 A394863 A394864 * A394866 A394867 A394868

Keyword

nonn,easy

Author

Yifan Xie, Jun 12 2026

Status

approved