# Number of integers less than $1000$ with a certain property

A positive integer is called cyclic if it is not divisible by the square of any prime, and whenever $p<q$ are primes that divide it, $q$ does not leave a remainder of $1$ when divided by $p$. Compute the number of cyclic numbers less than or equal to $1000$.

Firstly note that a cyclic positive integer $n$ must be squarefree and so has at most $4$ prime factors, since $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 > 1000$. Thus if $n$ has exactly one prime factor $p_1$, there are $\pi(1000)$ such cyclic integers. If $n$ has exactly two prime factors $p_1 < p_2,$ let $p_2 = p_1k+r,$ where $1 < r \leq p-1$. Then $p_1 \leq 29$. But it seems hard to count primes with this property.

• It doesn't seem to me that just bruteforcing the whole problem, finding all factorizations with the sieve of Eratosthenes and just checking if they are cyclic is much longer than calculating $\pi(1000)$. Do you need a program that outputs the answer? Then it is straitforward to write such. Do you need to do this by hand? I don't think that calculating even $\pi(1000)$ is a great fun. – Wolfram Jan 29 '17 at 1:43
• Inclusion Exclusion might be easier. Just take $1000$ less those divisible by some specified $p^2$ plus those divisible by some specified pair of primes, and so on. – lulu Jan 29 '17 at 1:51
• @lulu I think that is harder because then also have the case that there exist primes $p,q$ such that $p < q$ are primes that divide it and $q$ leaves a reminder of $1$ when divided by $p$. – Puzzled417 Jan 29 '17 at 2:01
• Well, to be cyclic it must be square free and composite. It doest actually seem that hard to list them all. – fleablood Jan 29 '17 at 2:33

• $1$ is perhaps cyclic ($1$ case) - except of course that $1\equiv 1 \bmod p$ (any prime), but fortunately no primes divide $1$. I suggest a check on the motivation for the definition to decide this case.
• Every prime $p$ is cyclic ($168$ cases)
• $2$ is the only even cyclic number. Proof: multiplying by $2$ gives a square and every other prime is $\equiv 1 \bmod 2$. This also easily eliminates any $4$-prime cases since $3\cdot5\cdot 7\cdot 11 > 1000$
• $pq$ where $p,q$ are distinct (odd) primes: a reasonable number of cases, but the smaller prime must be in $\{3,5,7,11,13,17,19,23,29\}$ giving $\{34,33,25,16,14,9,7,5,1\}$ cases respectively, (total $144$)
• $pqr$ where $p<q<r$ are distinct (odd) primes: $pq$ is confined to $\{15,33,35,51\}$ giving $\{6,2,4,0\}$ cases respectively, (total $12$).
Total of $324$ cyclic numbers under $1000$, or $325$ if $1$ is cyclic.
• It pretty much is casework for the counts. The driving values are found considering the potential for finding a larger prime to keep the result under $1000$. Excel is marvellous for automating such things, with a bit of user skill. – Joffan Jan 29 '17 at 2:45