liczba rozkładów liczby 50! :: 4programmers.net

0

liczba rozkładów liczby 50!

Obliczenie tego na kartce papieru zajeloby z ladnych 20 minut, wiec sprawa sprowadza sie do napisania prostej funkcji. wyszlo mi 108 - bylbym rad, gdyby ktos mogl potwierdzic moj wynik :)

0

Uściślijmy.
Rozkład = rozkład na czynniki pierwsze?
Dla 4! liczba rozkładów wynosi 4, bo 4!=3222 = 2322 = 2232 = 2223?
Jeżeli o to chodzi, to, imo, wynik 108 jest dużo za mały.

0

Rozkład liczby na liczby pierwsze jest zawsze jeden - podstawowe twierdzenie analizy (nie pamiętam dokładnie nazwy)
Rozkład liczby na liczby pierwsze z uwzględnieniem kolejności czynników - obliczamy wszystkie dzielniki pierwsze (ile których jest) kolei dla 1!..50! dodając do wartości poprzedniej, następnie stosujemy wzór na permutacje z powtórzeniami
Rozkład liczby na dowolne liczby - zapewne trzeba będzie zastosować programowanie dynamiczne

0

Jeżeli o to chodzi, to, imo, wynik 108 jest dużo za mały.

Moze wytlumacze swoja metode. Poniewaz liczba 50! jest dosc duza, wiec obliczenia rozlozylem na poczeszczegolne liczby. Jesli sie nie myle, to liczba czynnikow pierwszych nie zmieni sie, jesli oblicze ich ilosc np. z 65432 ( 2+1+2+1+1 = 7) zamiast z calej liczby 720 ( 2^{4 * 3}2 * 5, czyli rowniez 7 :) ). Dlatego porozkladalem 50! na 504948... co dawalo odpowiednio liczbe czynnikow 3+2+5... itd. Wynik wyszedl 108. Liczac recznie moglbym popelnic blad, wiec szukam potwierdzenia, ze wynik jest dobry :)

EDIT.

Rozkład liczby na liczby pierwsze jest zawsze jeden - podstawowe twierdzenie analizy (nie pamiętam dokładnie nazwy)

Rozkład liczby na liczby pierwsze z uwzględnieniem kolejności czynników - obliczamy wszystkie dzielniki pierwsze (ile których jest) kolei dla 1!..50! dodając do wartości poprzedniej, następnie stosujemy wzór na permutacje z powtórzeniami

Rozkład liczby na dowolne liczby - zapewne trzeba będzie zastosować programowanie dynamiczne

Hm... Rzeczywsicie, jak teraz patrze, to nie wzialem pod uwage, ze liczba rozkladow niekoniecznie musi byc ta na czynniki pierwsze. Jesli dolozyc permutacje oraz rozklad na dowolne liczby, to ilosc rozkladow moze wzrosnac i to znacznie.... -_-'

0

$50!=2{47}\cdot2{22}\cdot5{12}\cdot78\cdot114\cdot133\cdot172\cdot192\cdot23^2\cdot29\cdot31\cdot37\cdot41\cdot43\cdot47$
Suma wykładników (liczba czynników pierwszych, uwzględniając wielokrotne) to 108

0

50! dzieli się bez reszty przez 4464046080 liczb.
Ich suma to 218174515904456969581674334837521529647143055709686266261790720000

0

mgr.Dobrowolski napisał(a)

$50!=2{47}\cdot2{22}\cdot5{12}\cdot78\cdot114\cdot133\cdot172\cdot192\cdot23^2\cdot29\cdot31\cdot37\cdot41\cdot43\cdot47$
Suma wykładników (liczba czynników pierwszych, uwzględniając wielokrotne) to 108

Poprawiłem literówkę.
$50!=2{47}\cdot3{22}\cdot5{12}\cdot78\cdot114\cdot133\cdot172\cdot192\cdot23^2\cdot29\cdot31\cdot37\cdot41\cdot43\cdot47$

0

Wszystko fajnie, ale co to ma wspólnego z C++?

0

(A022559)

int isprime(int n){
	int d;
	if (n<2) return 0;
	if (n<4) return 1;
	if (n%2==0 || n%3==0) return 0;
	d=5;
	while(d*d<=n){
		if (n%d==0) return 0;
		d+=2;
		if (n%d==0) return 0;
		d+=4;
	}
	return 1;
}

int bigomega(int n){
	int s=0, p, i;
	for(p=2; p<=n; p++)
		if (isprime(p)){
			i=p;
			while (i<=n){
				s+= n/i;
				i*= p;
			}
		}
	return(s);
}

0

bogdans napisał(a)

[...]Poprawiłem literówkę.[...]
Dzięki

Gdy kolejność ma znaczenie, wtedy iczbę 6 można przedstawić jako iloczyn na 3 sposoby - 6, 23, 32.
12 na 8 sposobów, a 7 już tylko w jeden (bo 7 jest pierwsze)

Szybko wymyśliłem

uint H(uint n){
	uint i,s=1;
	for(i=2;i<=n/2;i++)
		if (n%i==0)
			s+= H(n/i);
	return s;
}

50! da się zapisać jako iloczyn na
141682028500548560448648966155832105449578039785685404062569013249980803637735670120155289523060736 sposobów.
Sporo, mój komputer policzył to w 0 mS :-)

Przy okazji wysłałem poprawkę do MathWorld Team'u, znalazłem błąd w opublikowanym wzorze.
Pozdrawiam, mag.D

0

Jeżeli bierzemy pod uwagę tylko rozkłady na czynniki pierwsze, to 50! można przedstawić tylko na
204811506473095216372076499624802293795414107772965156871889328070451200000000 sposobów.
P.S., mój komputer (program w Javie) też liczył 0 ms.

0

No to czekamy na faktoryzację gdzie kolejność NIE MA znaczenia.

uint U(uint n, uint m){
	uint i,s=0;
	for(i=2;i<=n/2;i++)
		if (n%i==0 && i<=m)
			s+= U(n/i, i);
	if (n<=m) s++;
	return s;
}

Na koniec trzeba dodać jeden.

Ale się chyba nie doczekamy

0

Dziekuje za odpowiedzi - wielkosc wynikow wrecz mnie porazila XD

0

Chyba udało mi się napisać funkcję rekurencyjną liczącą ilość rozkładów danej liczby na czynniki (kolejność nie ma znaczenia). W tej chwili jest zaimplementowana tylko dla typu int. Wyniki

2!                       0
3!                       1
4!                       6
5!                     20
6!                     97
7!                    391
8!                  2115
9!                 11829
10!               70519
11!              425239
12!             2787809

Nie dopuszczam rozkładów z użyciem 1, jeśli rozkład 6=6 byłby dopuszczalny, to również rozkłady 6=61, 6=61*1,.. byłyby dopuszczalne. Wówczas problem staje się banalny - dla każdej liczby n ilość rozkładów wynosi $\infty$

0

Zmieniłem typ na long, puściłem dla najwiekszej dopuszczalnej wartości (20!) i czekam już na wynik 20 godzin. Jest zatem wyzwanie - napisać algorytm tak, by wynik dla 50! dostać przed końcem tego stulecia.

0

Możesz pokazać kod? Wadzi mi parametr "m" w mojej funkcji U(m, n)

0

Na wyni dla 20! czekałem 4 doby i sie nie doczekałe, Byłem potem mniej ambitny.
12! 10 sekund
14! 1506 sekund
15! 23830 sekund (około 4 godzin)
Z dalszych eksperymentów zrezygnowałem.
Pętla wyglada tak:

        long ile=silnia(k);
        long wynik=0;
        for(long i=ile/2;i>=2;i--)
            if(ile%i==0)
            {
                wynik+=f(ile/i,Math.min(i,ile/i),true);
            }

maxPrime, to największa liczba pierwsza w rozkładzie na czynniki liczby ile,
tablica haszujaca wyniki ma typ HashMap<ArrayList<Long>,Long>, rezygnacja z niej wydłuża czas działania programu o jakieś 10%.
funkcja rekurencyjna f wygląda tak:

    private long f(long n,long k,boolean first)
    {
        ArrayList<Long> al=new ArrayList<Long>();
        al.add(n);
        al.add(k);
        if(wyniki.get(al)!=null)
            return wyniki.get(al);
        long w=0;
        if(n==1)
        {
            if(!first)
                w=1;
            wyniki.put(al,w);
            return w;
        }
        if(n<=maxPrime && pierwsze.get(n)) //pierwsze.get(n) <==> czy n jest liczbą pierwszą
        {
            if(k==n)
                w=1;
            wyniki.put(al,w);
            return w;
        }
        if(k<=n)
        {
            for(long i=k;i>=2;i--)
                if(n%i==0)
                    w+=f(n/i,Math.min(i,n/i),false);
        }

        wyniki.put(al,w);
        return w;
    }

0

hym, hym,
myślałem, że mimo żem stary to rozumiem jeszcze to i owo, jednak tak zapisany algorytm jest dla mnie "trochę" nieczytelny.
cóż, trochę piwa było, ale tak czy siak pewnie będę miał kłopot
50! ma jakieś 4*10^9 dzielników, trzeba przewędrować przez wszystkie,
beznadziejne zadanie
idę o zakład, że będzie tak jak napisałem wcześniej:
"się nie doczekamy"

0

Jutro (dzisiaj?) postaram sie wyjaśnić.

0

Niech $n = l_1l_2...* l_m$ będzie faktoryzacją liczby $n$ . Funkcja
$f(n,k)$ ma zwracać ilość takich faktoryzacji liczby $n$ , że $l_1>=l_2>=...>=l_m$ oraz $l_1<=k$ ..
Mam wrażenie, że główna pętla

long wynik=0;
for(long i=ile/2;i>=2;i--)
      if(ile%i==0)
      {
           wynik+=f(ile/i,Math.min(i,ile/i));
      }

nie wymaga wyjaśnień.
Uproszczona wersja funkcji $f(n,k)$ wygląda tak:

 private long f(long n,long k)
{
     long w=0;
     if(n==1)
         return 1;
     if(n<=maxPrime && pierwsze.get(n))
         if(k==n)
             return 1;
         else
             return 0;
     if(k<=n)
     {
         for(long i=k;i>=2;i--)
             if(n%i==0)
                 w+=f(n/i,Math.min(i,n/i));
     }
     return w;
}

Usunąłem zbyteczny parametr logiczny first, oraz odwołania do HasMapy wyniki. Ta HasMapa nie miała żadnego znaczenia dla istoty algorytmu, trochę (10%) przyspieszała działanie algorytmu, po wywołaniu f(n,k) funcja sprawdzała we wspomnianej HashMapie czy przypadkiem jwczesniej nie było takiego wywołanie. Jeśli było, to zwracała zapamiętany wynik. (Trochę mnie ciekawi, że mimo iż nie zwiększyłem rozmiaru sterty, to mimo trwających cztery doby obliczeń nie wystąpił brak pamięci).
Pierwszy if jest oczywisty.
Drugi if sprawdza czy liczba $n$ jest pierwsza - mój programik dopuszcza uruchomienie pr 11! i wtedy liczy ilość faktoryzacji liczby 11!, oraz pr 37923 i wtedy liczy ilośc fakryzacji liczby 37923. W efekcie w programie może wystąpic dużo liczb pierwszych. Na starcie programu wyznaczam przy pomocy sita wszystkie liczby pierwsze z odpowiedniego zakresu.
Trzeci if, to rekurencja.

0

Czyli robimy to samo, tak samo.

Twój pomysł z liczbami pierwszymi poprawia sprawę odrobinę.
Licząc dla "p" nie pojawi się liczba pierwsza większa od p.

Zapamiętywanie wyników to też tylko półśrodek.

Głębokość rekurencji to dokładnie tyle ile liczb pierwszych
w faktoryzacji silni, bigomega(20!)=36, bigomega(50!)=108.

Podstawowy problem to naiwne szukanie dzielników,
ale przecie znamy rozkład "p!" na czynniki pierwsze,
czyli potrafimy wyliczyć wszystkie dzielniki n.
Siadam zaraz i spróbuję to zapisać.

Teraz robiłem tak (usunąłem drobne optymalizacje)

uint U1(uint n, uint m){ 
	uint i,s;
	if (n<48 && primes[n]) return n<=m; // twoje
	g++; if (g>gm) gm=g;  // mierzy głębokość rekurencji

	s= n<=m;
	m=min(m, n/2);
	for(i=2;i<=m;i++)
		if (n%i==0)
			s+= U1(n/i, i);
	g--;
	return s;
}

wołam U1(p!, p!/2)

0

Jeszcze jedno, skoro i dzieli n, to także n/i jest dzielnikiem n

uint U2(uint n, uint m){
	uint j,i,s;
	s= n<=m;
	m=min(m, n/2);
	i=2; j=n/2;
	while(i<=m && i<=j) {
		if (j*i==n) {
			s+= U(j, i);
			if (j!=i && j<=m) 
				s+= U(i, j);
		}
        i++; j=n/i;
	}
	return s;
}

Czas w sekundach oraz liczba wywołań funkcji2! 0 0.000 1 3! 1 0.000 3 4! 6 0.000 14 5! 20 0.000 53 6! 97 0.000 294 7! 391 0.000 1371 8! 2115 0.000 8528 9! 11829 0.010 53738 10! 70519 0.070 354720 11! 425239 0.520 2330767 12! 2787809 4.096 16742403

Liczba wywołań rośnie obrzydliwie, chyba jeszcze sporo pracy.

0

Rozpędzam się jakieś 10 sekund i mam:2! 0 0.000 1 3! 1 0.000 1 4! 6 0.000 1 5! 20 0.000 1 6! 97 0.000 1 7! 362 0.000 69 8! 2066 0.000 378 9! 11496 0.000 3060 10! 69029 0.010 24512 11! 416199 0.140 218175 12! 2744149 0.601 1686119 13! 19199923 5.949 16061162 14! 142740186 54.298 143895695 15! 1135471406 495.242 1333916726

0

pośpieszyłem się z poprzednim postem :-( [wstyd]

0

start... (6000) 141 sekund rozbiegu
 2!                0    0.000            1
 3!                1    0.000            1
 4!                6    0.000            1
 5!               20    0.000            1
 6!               97    0.000            1
 7!              391    0.000            1
 8!             2115    0.000          111
 9!            11829    0.000          702
10!            70519    0.000         6461
11!           425239    0.020        64040
12!          2787809    0.200       517330
13!         19530212    2.163      5401264
14!        144890225   21.060     51195177
15!       1149973311  184.926    495712771
16!       8558047182 1466.899   -160718018

Doczekałem się U(17!)=7'641'751'6718, w czasie 810+13711 sekund, czyli około czterech godzin.
Te wyniki uzyskałem obliczając w czasie rozbiegu tablicę dla małych wartości N i M, małych to znaczy kilka tysięcy.

A teraz zrobiłem inaczej.
Wyliczam wszystkie dzielniki P!, później potencjalnych dzielników szukam w tej tablicy

12!    6 sek
13!   45 sek
14!  358 sek (6 min)
15! 3135 sek (52 min)

Połączenie obu sposobów pewnie umożliwiłoby doczekanie się na faktoryzację 20!, ale 50! dalej pozostaje poza zasięgiem.

liczba rozkładów liczby 50!

mgr.Dobrowolski napisał(a)

bogdans napisał(a)

1 użytkowników online, w tym zalogowanych: 0, gości: 1

Praca dla programistów

Forum dyskusyjne

Sprawy administracyjne

O nas

Skontaktuj się z nami