Highly Divisible Number

For the final constraint to be followed, it is obvious that we should have 2 in the prime factorization. Let's assume all the 10000 factors are 2s right now. Now for the second constraint to hold always, the number itself should always be divisible by the number of factors. So we transfer the minimum number of prime powers from 2 to other prime factors to make it divisible by the number of factors (in this case 4 prime powers are transferred from 2 to 5). Now, we divide the number of prime factors by the number and update the remaining factorization and the number of remaining divisors (In this case the new factorization after division by 10000 becomes $2^{9992} \times \ 5^{0}$ and the number of divisors become 9992 ). Then repeat this till the number of factors become 1 i.e the number becomes 2.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

#include<bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define ll long long
#define INF 2000000000
#define INF2 2000000000000000000

using namespace std;

int freq[10001];
int factorization[10001];

vector<pair<int,int>>primeFactors[10001];
bool prime[10001];

void Sieve()
{
    memset(prime,true, sizeof(prime));
    for(int i = 2; i <= 100; i++)
    {
        if(prime[i])
        {
            for(int j = 2; i*j <= 10000; j++)
                prime[i*j] = false;
        }
    }
    for(int i = 2; i <= 10000; i++)
    {
        if(prime[i])
        {
            for(int j = 1; i*j <= 10000; j++)
            {
                int temp = i*j;
                int ct = 0;
                while((temp%i) == 0)
                {
                    ct++;
                    temp /= i;
                }
                primeFactors[i*j].push_back({i, ct});
            }
        }
    }
}

int main()
{
    IOS;
    #ifndef ONLINE_JUDGE
        //freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    Sieve();
    int n = 10000;
    freq[2] = 10000;
    factorization[2] = 10000; 
    while(n > 1)
    {
        for(auto it:primeFactors[n])
        {
            if(freq[it.first] >= it.second)
                continue;
            int diff = (it.second - freq[it.first]);
            freq[2] -= diff;
            factorization[2] -= diff;
            freq[it.first] += diff;
            factorization[it.first] += diff;
        }
        int tot = 0;
        for(auto it:primeFactors[n])
        {
            tot += it.second;
            freq[it.first] -= it.second;
        }
        n -= tot;
    }
    for(int i = 2; i <= 10000; i++)
    {
        if(prime[i] && (!factorization[i]))
        {
            cout << i;
            return 0;
        }
    }
}   

My code is not that long in python 3.4

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

from pyprimes import factors, isprime

def solve():
    "Highly Divisible Number"
    pan = 10000
    allfact = set()
    while pan > 1:
        allfact = allfact.union(factors(pan))
        pan -= len(factors(pan))

    return min(n for n in range(2, max(allfact)+1) if not n in allfact and isprime(n))

print(solve())

My code is a bit long, so here's the gist of what needs to be done to solve this problem.

First, create a method that gives the prime factorization of a number and saves the factors to a list; also note the multiplicities of each factor. Then, starting with the number $n=10000$ , create a loop that ends when $n=1$ that does the following things:

1. Calculate $P(n)$ by finding the list of prime factors and calculating the size of the list, counting multiplicities.

2. Subtract $P(n)$ from $n$

3. Add the prime factors of $n$ to a list of all factors that you have previously seen.

After $655$ steps this loop should terminate. Using this method you will eventually generate all of the prime factors necessary to create our number $n$ . Finally, generate a list of primes from $2$ to $10000$ (while the list doesn't need to be that big, I did it just to be safe) and check your list of factors against the list of all primes to see which is the first prime to not appear in your list. The first prime that doesn't appear is $\boxed{997}$ , giving us our final answer.