facultatief deelbaar

[David]

n en d zijn positieve gehele getallen. Hoe vaak is n! deelbaar door d?

[barto]

Als p de grootste priemfactor is van d kom ik bij benadering op
n*p/(p-1)²
als de getallen groot genoeg zijn.
Maar om er iets exacts op te plakken lijkt mij moeilijk omdat je met zo'n moeilijke som zit.

[arie]

Als d=1 is het antwoord oneindig.
Als d>1: ontbind d in factoren:



Schrijf vervolgens n! als product van deze priemfactoren en een restfactor q:



Al de m machten bepaal je via:



waarbij alle termen boven een te bepalen nul zullen zijn.

De macht r die je zoekt is dan:



Nu is wel deelbaar door maar NIET deelbaar door

[Sjoerd Job]

Naast arie zijn juiste opmerking, heb ik ook eens het volgende 'geniale' antwoord gehoord:

'nul of oneindig vaak'. De toelichting was de volgende: als ik n! kan delen door d, kan ik n! zo vaak als ik wil delen door d, want er komt toch altijd hetzelfde uit.

5! / 4 = 30 (eerste keer)
5! / 4 = 30 (tweede keer)
5! / 4 = 30 (derde keer)
...
...

[arie]

Ben ik erin getrapt ...

[barto]

Als p de grootste priemfactor is van d kom ik bij benadering op
n*p/(p-1)²
als de getallen groot genoeg zijn.
Maar om er iets exacts op te plakken lijkt mij moeilijk omdat je met zo'n moeilijke som zit.

=fout.

Laat p het maximum zijn van alle met de priemontbinding van n.
Dan is het een kwestie van (en niet wat ik eerst deed) want alle andere zullen minstens zoveel voorkomen als p.
En dat is ongeveer .

[David]

Ben ik erin getrapt ...

Nee hoor, Arie, dit is het antwoord dat ik ook in gedachten had. Ik had de vraag uit de link.

Er is nog een iets andere manier om de grootste r te bepalen zodat voor priem p.

Stel: , en
Dan is r gelijk aan

met

[arie]

Mooi.

Hieronder mijn code in Pari/GP, mocht je die kunnen gebruiken.
Hierin is r = facdeel(n,d).
Wegens mogelijke nauwkeurigheidsproblemen omzeil ik liever de log-functies in dit soort vraagstukken.


Nog iets voor de verzameling curieuze getallen:
Neem





dan is

Code: Selecteer alles

primdeel(n,p)={
local(pp,r);

r=0;
pp=p;
while(pp<=n,
  r+=(n\pp);
  pp*=p;
  );
r
}


facdeel(n,d)={
local(M,l,r,f);

if(d==1,
  r=-1, \\ := infinity
  \\else:
  M=factor(d);
  l=length(M~);
  f=primdeel(n,M[1,1]);
  r=f\M[1,2];
  for(i=2,l,
    f=primdeel(n,M[i,1]);
    r=min(r, f\M[i,2]);
    );
  );
r
}

{
n=123456;
d=111111;
r=facdeel(n,d);
print(r);
print("dit is 1: ",denominator(n!/(d^r)));  \\noemer van deze gereduceerde breuk = 1
print("dit is >1: ",denominator(n!/(d^(r+1)))); \\noemer van deze gereduceerde breuk > 1

r=facdeel(10^10, 2^(3^4));
print(r);

}

[David]

Bedankt, voor de code.

Ik had eerst dit gemaakt

Code: Selecteer alles

{
div=(n,b)->
q=floor(log(n)/log(b));
div=0;
c=n;
for(i=1,q,
 c=floor(c/b);
 div=div+c;
   )
}

{
r=factor(56);
bases=matsize(r)[2];
maxi=0;
for(k=1,bases,
 if(r[k,2]>maxi,
  maxi=r[k,2];
   )
   );
maxi
}

Dat gaf een bug in pari, door mijn functie div, dus ik heb advies gevraagd. Ik kreeg dit (equivalent aan jouw functie primdeel):

Code: Selecteer alles

{
div=(n,b)->
  my(q=floor(log(n)/log(b)), div=0, c=n);
  for(i=1,q,
    c=floor(c/b);
    div=div+c;
  );
  div
}

Een alternatief dat gegeven werd voor deze functie is nog

Code: Selecteer alles

div(n,p)={
  my(s);
  while(n\=p, s+= n);
  s
};

Ik zou zelf matsize gebruiken voor de lengte van een matrix, bijv. gegeven door de functie factor, dan kan je zowel de lengte als de breedte opvragen.