Maximal $k$-Multiple-Free Sets of Integers

Abstract

Let $k$ be an integer greater than one. A set $S$ of integers is called $k$-multiple-free (or $k$-MF for short) if $x\in S$ implies $kx\notin S$. Let $f_k(n)=max\{|A|:A\subseteq [1,n]\text{ is }k\text{-MF}\}$. A subset $A$ of $[1,n]$ with $|A|=f_k(n)$ is called a maximal $k$-MF subset of $[1,n]$. In this paper, we give a recurrence relation and a formula for $f_k(n)$. In addition, we give a method for constructing a maximal $k$-MF subset of $[1,n]$.