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

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

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
16:36:42
Зарегистрироваться »

*есть доп. регистрация

→ Трансляции

Leetcode BiWeekly Contest 144 — Solution Discussion

Shayan

До начала 18:06:42

Codeforces CodeTON Round 9 (Div 1 + Div 2) — Solution Discussion

Shayan

До начала 19:36:42

Всё →

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

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

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

Всё →

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

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Всё →

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

→ Прямой эфир

Детальнее →

Блог пользователя 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

Спойлер

/*
    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.

→ Ответить