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.

  • $\begingroup$ 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. $\endgroup$ – Wolfram Jan 29 '17 at 1:43
  • $\begingroup$ 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. $\endgroup$ – lulu Jan 29 '17 at 1:51
  • $\begingroup$ @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$. $\endgroup$ – Puzzled417 Jan 29 '17 at 2:01
  • $\begingroup$ Well, to be cyclic it must be square free and composite. It doest actually seem that hard to list them all. $\endgroup$ – fleablood Jan 29 '17 at 2:33

By cases:

  • $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.

  • $\begingroup$ Is there any easy way to get the sets you have in the cases? It seems like a lot of casework. $\endgroup$ – Puzzled417 Jan 29 '17 at 2:36
  • $\begingroup$ 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. $\endgroup$ – Joffan Jan 29 '17 at 2:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.