Find a counterexample: For every antiprime $n>1$, there is a prime divisor $p$ such that $n/p$ is an antiprime

divisibilityelementary-number-theoryexamples-counterexamplesnumber theory

When dinosaurs ruled the earth, one of my assignments in a Problem Seminar in undergraduate was to devise and prove a conjecture about antiprimes, and this was my attempt:

An antiprime (also called a highly composite number) is a positive integer that has more divisors than any number less than it. The first few antiprimes are $$1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360,…$$ Conjecture: For every antiprime $n>1$, there is a prime $p$ such that $p\mid n$ and $n/p$ is an antiprime.

Anyways, I never found a proof for that, and about ten years ago I asked the xkcd math forums if they could guide me. Instead, someone posted a counterexample that was quite enormous.

A question on MESE is asking about relatively elementary mathematical conjectures whose smallest counterexamples are large numbers. I'd like to suggest my problem, but the xkcd forums went down five months ago over a data breach and my thread wasn't cached by Google or the Wayback Machine.

Can someone find that counterexample? The person who posted didn't indicate if they came up with their number through mathematical reasoning or programming. I discovered this morning that OEIS has a list of the first ten thousand antiprimes, so in theory it may just come down to finding the prime decomposition of each of them. But, if possible, is there a mathematical argument that would lead one to the correct number?

Best Answer

My original answer was different since it was based on flawed code snippet for generating these numbers. However I've looked at the list that you have found as well, parsed it and found that smallest counterexample to your conjecture is $$362279431624673937974303738230488502933082643722886373107941760000$$ which is the $815$th highly composite number. To check quickly from the given list, no prime decomposition is necessary. All we need to do is check that none of the $n/d$ is prime for all antiprimes $d<n$. Otherwise, we could take $p=n/d$ and it would satisfy the condition of conjecture. Same works in the opposite direction: if there would be a prime $p$, take $d=n/p$, and since clearly $d<n$, we have $n/d=p$ is a prime.

Unfortunately, I do not know if there is a mathematical reasoning alone that could help you to get to that number. The above is just assuming we already have a list.

Here is a Python snippet I used:

import sympy

L=set()
for line in open("b002182.txt").readlines():
    n = int(line.split()[1])
    isok = False
    for prev in L:
        if n % prev == 0:
            if sympy.isprime(n // prev):
                isok = True
                break
    if not isok and n > 1:
        print(line)
        break

    L.add(n)

Here is also list of (smallest) witness primes $p$ for all the preceeding numbers, $n/p$ and also prime divisors: https://gist.github.com/TheSil/f26dc0a516d12a9a556ada3191512c99

Check also An Algorithm for Computing Highly Composite Numbers article, and on the site related post is there a large list of highly composite number?.

Related Question