smallest K such that number of arrangements of prime factors of K equals N?

→ Обратите внимание

До соревнования
Codeforces Round (Div. 3)
36:24:35
Зарегистрироваться »

→ Трансляции

CodeChef Starters 132 Solution Discussion

aryanc403

До начала 14:34:35

Codeforces Round 943 Solution Discussion

aryanc403

До начала 38:49:35

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	ecnerwala	3649
2	Benq	3581
3	jiangly	3578
4	orzdevinwang	3570
5	Geothermal	3569
5	cnnfls_csy	3569
7	tourist	3565
8	maroonrk	3531
9	Radewoosh	3521
10	Um_nik	3482

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	maomao90	174
2	awoo	165
3	adamant	161
4	TheScrasse	160
5	nor	158
6	maroonrk	156
7	-is-this-fft-	152
8	orz	146
8	SecondThread	146
10	pajenegod	145

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя pabloskimg

smallest K such that number of arrangements of prime factors of K equals N?

Автор pabloskimg, история, 6 лет назад, По-английски

Basically the title. The problem statement can be found here. No idea how to solve it efficiently.

UPDATE 1: why the downvotes?

UPDATE 2: based on the answers so far, the solution would be to exhaustively explore all combinations of exponents k₁, k₂, ..., k_r (k_i ≥ k_j for all i < j) such that $\text{[math]}$ and k = 2^k₁ * 3^k₂ * 5^k₃ * 7^k₄ * 11^k₅ * ... < 2⁶³. During the exhaustive search one can map each n to its minimum k found (for instance, using an unordered_map) and then the queries can be answered in O(1). The problem is: how can you estimate the complexity of the exhaustive search? Any easy way to estimate an upperbound for it?

UPDATE 3: pshishod2645 says there are around 2 * 10⁶ valid combinations of exponents, where did he get that number from?

#math, #combinatorics, #primes

pabloskimg
6 лет назад
7

Комментарии (7)

Написать комментарий?

fugazi

6 лет назад, # |

Let the prime factorisation of n be p₁^n₁p₂^n₂....p_k^n_k, then we have $\text{[math]}$ , which means that f(n) doesn't depend on primes but instead on the exponents. So you can find all numbers ( < 2⁶³)which are formed by first few primes, Mathematically , you have to find all such numbers such that if the prime factorisation of n contains prime p, then it must contains all primes less than p. The number of such numbers is around 2 * 10⁶, so you preprocess f(n) for all those n and get the answer for all given n in O(1). My code for finding such numbers is in spoliler

Spoiler

/*
    A story, which will never end
    A story, which never began
*/

#include <bits/stdc++.h>

using namespace std;

#define IOS ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define endl '\n'
#define ll long long

vector<unsigned long long> v, prime;

const int N = 100;
__int128 MAX = 1;

void find(int id, __int128 num){
    if(num > MAX)return;
    v.push_back(num);
    while(num < MAX){
        num = num*prime[id];
        find(id + 1, num);
    }
}

void sieve(){
    int vis[N];
    fill(vis, vis + N, 0);
    for(int i=2;i<N;++i)if(!vis[i]){
        prime.push_back(i);
        for(int j=i;j<N;j += i)
            vis[j] = 1;
    }
}

int main(){
    IOS;
    for(int i=1;i<=63;++i) MAX*= 2;
    sieve();
    find(0, 1);
    cout<<v.size()<<endl;
    return 0;
}

→ Ответить

pabloskimg

6 лет назад, # ^ |

← Rev. 3 →

"So you can find all numbers (< 2^63) which are formed by first few primes" What do you mean by first few primes? Which are those first few primes?

"you have to find all such numbers such that if the prime factorisation of n contains prime p, then it must contains all primes less than p" Why do I have to find these numbers?

Would you mind elaborating your points a little more?

→ Ответить

fugazi

6 лет назад, # ^ |

The value of f(n) is same for n = 2³ * 5⁷, 2³ * 5⁷, 31³ * 47⁷, so the actual primes doesn't matter but their exponents do, so you have to find all such numbers which contains all primes from 2 to largest prime factor in their factorisation. for example you have to consider n = 2³ * 3⁷ but not 2³ * 5⁷, because in second 5 is present but 3 is missing.

→ Ответить

pabloskimg

6 лет назад, # ^ |

← Rev. 2 →

Would you mind explaining how you calculate/estimate that there are around 2 * 10⁶ such numbers? I think knowing how to do this estimation is crucial before one can decide to use this approach.

→ Ответить