Englobante ce programme pour déterminer la somme des entiers réciproques ne contenant pas de zéro
https://stackoverflow.com/questions/3847615
-
27-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Soit A désigne l'ensemble des entiers positifs dont la représentation décimale ne contient pas le chiffre 0. La somme des inverses des éléments A est connu pour être 23,10345.
Ex. 1,2,3,4,5,6,7,8,9,11-19,21-29,31-39,41-49,51-59,61-69,71-79,81-89, 91-99,111-119, ...
Ensuite, prendre l'inverse de chaque numéro, et la somme du total.
Comment cela peut-il être numériquement vérifié?
Ecrire un programme d'ordinateur pour vérifier ce chiffre.
Voici ce que je l'ai écrit à ce jour, je besoin d'aide englobante ce problème car cela prend trop de temps à l'heure actuelle complète:
code en Java
import java.util.*;
public class recip
{
public static void main(String[] args)
{
int current = 0; double total = 0;
while(total < 23.10245)
{
if(Integer.toString(current).contains("0"))
{
current++;
}
else
{
total = total + (1/(double)current);
current++;
}
System.out.println("Total: " + total);
}
}
}
La solution
Ce n'est pas si difficile lorsqu'il est sollicité correctement.
Supposons par exemple que vous voulez trouver la somme de tous les entiers réciproques de départ (à savoir les plus à gauche chiffres) avec 123 et se terminant par k chiffres non nuls. De toute évidence, il y a 9 k de tels nombres entiers et l'inverse de chacun de ces entiers est dans la plage 1 / (124 * 10 k ) .. 1 / (123 * 10 < sup> k ). D'où la somme des inverses de tous ces entiers est limitée par (10/09) k / 124 et (10/09) k / 123.
Pour trouver des limites pour la somme de tous en commençant par 123 inverses il faut ajouter les limites ci-dessus pour chaque k> = 0. Ceci est une série géométrique, d'où on peut déduire que la somme des inverses des nombres entiers commençant par 123 est délimitée par 10 * (10/09) k / 124 et 10 * (9/10) < sup> k / 123.
La même méthode peut bien sûr être appliqué pour toute combinaison de chiffres le plus à gauche. Les autres chiffres que nous examinons à gauche, le résultat devient plus précis. Voici une mise en œuvre de cette approche en python:
def approx(t,k):
"""Returns a lower bound and an upper bound on the sum of reciprocals of
positive integers starting with t not containing 0 in its decimal
representation.
k is the recursion depth of the search, i.e. we append k more digits
to t, before approximating the sum. A larger k gives more accurate
results, but takes longer."""
if k == 0:
return 10.0/(t+1), 10.0/t
else:
if t > 0:
low, up = 1.0/t, 1.0/t
else:
low, up = 0, 0
for i in range(10*t+1, 10*t+10):
l,u = approx(i, k-1)
low += l
up += u
return low, up
Appel à (0, 8) par exemple donne la limite supérieure et inférieure: 23,103447707 ... et 23,103448107 .... qui est proche de la revendication 23,10345 donnée par l'OP.
Il existe des méthodes qui convergent plus rapidement à la somme en question, mais ils ont besoin de plus de mathématiques. Une approximation beaucoup mieux de la somme se trouve . Une généralisation du problème sont la série Kempner .
Autres conseils
Pour toutes les valeurs de plus de current que certains N seuil, 1.0/(double)current sera suffisamment faible pour que total n'augmente pas à la suite de l'ajout 1.0/(double)current. Ainsi, le critère de terminaison doit être quelque chose comme
while(total != total + (1.0/(double)current))
au lieu de tester dans la limite qui est connue a priori . Votre boucle s'arrête lorsque current atteint cette valeur particulière de N.
Je soupçonne que la coulée à chaîne, puis vérifier le caractère « 0 » est l'étape qui prend trop de temps. Si vous voulez éviter tous les zéros, pourrait aider à augmenter current ainsi:
(Edited - grâce à Aaron McSmooth)
current++;
for( int i = 10000000; i >= 10; i = i / 10 )
{
if ( current % i ) == 0
{
current = current + ( i / 10 );
}
}
Ceci est non testé, mais le concept doit être clair: chaque fois que vous frappez un multiple d'une puissance de dix (par exemple 300 ou 20000), vous ajoutez la prochaine puissance inférieure de 10 (dans nos exemples 10 + 1 et 1000 + 100 + 10 + 1, respectivement) jusqu'à ce qu'il n'y a plus de zéros dans votre numéro.
Changez votre boucle de while en conséquence et voir si cela ne les performances d'aide au point était votre problème devient gérable.
Oh, et vous voudrez peut-être limiter la sortie System.out un peu aussi. Est-ce que chaque dixième, ou hundreth 10000e itération soit suffisant?
Modifier la seconde:
Après un peu de sommeil, je soupçonne que ma réponse est peut-être un peu myope (blâmer l'heure tardive, si vous voulez). J'ai simplement espéré que, oh, un million d'itérations de current obtiendriez-vous à la solution et laissé à cela, au lieu de calculer les cas de correction à l'aide log( current ) etc.
À la réflexion, je vois deux problèmes avec tout ce problème. La première est que votre numéro cible de 23,10345 est un leeeeettle pour arrondir mes goûts. Après tout, vous ajoutez des milliers d'articles comme « 1/17 », « 1/11111 » et ainsi de suite, avec des représentations décimales infinies, et il est très peu probable qu'ils ajoutent à 23,10345 exactement. Si certains spécialistes des mathématiques numériques le dit, bien -. Mais je voudrais voir l'algorithme par lequel ils sont arrivés à cette conclusion
L'autre problème est lié à la première et concerne la limité en mémoire binaire représentation de vos nombres rationnels. Vous pouvez obtenir en utilisant BigDecimals , mais j'ai mes doutes.
Alors, au fond, je vous suggère de reprogrammer l'algorithme numérique au lieu d'aller pour la solution de force brute. Désolé.
Modifier le troisième: Par curiosité, je l'ai écrit cela en C ++ pour tester mes théories. Il est dirigé pendant 6 minutes maintenant et est à environ 14,5 (environ 550 itérations mio.). Nous verrons.
La version actuelle est
double total = 0;
long long current = 0, currPowerCeiling = 10, iteration = 0;
while( total < 23.01245 )
{
current++;
iteration++;
if( current >= currPowerCeiling )
currPowerCeiling *= 10;
for( long long power = currPowerCeiling; power >= 10; power = power / 10 )
{
if( ( current % power ) == 0 )
{
current = current + ( power / 10 );
}
}
total += ( 1.0 / current );
if( ! ( iteration % 1000000 ) )
std::cout << iteration / 1000000 << " Mio iterations: " << current << "\t -> " << total << std::endl;
}
std::cout << current << "\t" << total << std::endl;
Le calcul currPowerCeiling (ou cependant on pourrait appeler cela) à la main permet d'économiser quelques calculs de log10 et pow chaque itération. Chaque petit - mais il faut encore pour toujours ...
Modifier le quatrième: Etat est d'environ 66.000 itérations MIO total est jusqu'à 16,2583, l'exécution est à environ 13 heures. N'a pas l'air, Bobby S. - Je suggère une approche plus mathématique
. Souhaitez-vous stocker le nombre actuel comme un tableau d'octets où chaque élément de réseau est un chiffre de 0 à 9? De cette façon, vous pouvez détecter très rapidement des zéros (en comparant les octets en utilisant == au lieu de String.contains).
L'inconvénient serait que vous aurez besoin de mettre en œuvre la même incrémenter au lieu d'utiliser ++. Vous aurez également besoin de trouver un moyen pour marquer les chiffres « inexistants » de sorte que vous ne les détecte pas comme des zéros. Le stockage -1 pour les sons inexistants de chiffres comme une solution raisonnable.
Pour un entier signé 32 bits, ce programme ne cessera jamais. Il converge vers -2097156 en fait. Étant donné que le nombre maximal d'harmoniques (la somme des inverses entier de 1 à N) d'un entier signé de 32 bits est ~14.66, cette boucle ne sera jamais fin, même lorsque les enveloppes actuelles autour de 2^31 - 1 à -2^31. Depuis l'inverse de l'entier le plus grand 32 bits de négatif est ~ -4.6566e-10, à chaque fois de courant revient à 0, la somme sera négatif. Étant donné que le plus grand nombre représentable par un double tel que number + + 1/2^31 == number est 2^52 / 2^31, vous obtenez à peu près -2097156 la valeur de convergence.
Cela dit, et en supposant que vous ne disposez pas d'une manière directe du calcul du nombre harmonique d'un entier arbitraire, il y a quelques choses que vous pouvez faire pour accélérer votre boucle intérieure. Tout d'abord, l'opération la plus coûteuse va être System.out.println; qui doit interagir avec la console dans ce cas, votre programme devra éventuellement vider le tampon à la console (le cas échéant). Il y a des cas où cela ne peut pas se produire effectivement, mais puisque vous utilisez que pour le débogage, ils ne sont pas pertinents à cette question.
Cependant, vous passez aussi beaucoup de temps à déterminer si un nombre est un zéro. Vous pouvez retourner ce test autour de générer des gammes de nombres entiers tels que dans cette gamme vous garantit de ne pas avoir un nombre entier avec un chiffre zéro. C'est vraiment simple à faire progressivement (en C ++, mais assez trivial pour convertir en Java):
class c_advance_to_next_non_zero_decimal
{
public:
c_advance_to_next_non_zero_decimal(): next(0), max_set_digit_index(0)
{
std::fill_n(digits, digit_count, 0);
return;
}
int advance_to_next_non_zero_decimal()
{
assert((next % 10) == 0);
int offset= 1;
digits[0]+= 1;
for (int digit_index= 1, digit_value= 10; digit_index<=max_set_digit_index; ++digit_index, digit_value*= 10)
{
if (digits[digit_index]==0)
{
digits[digit_index]= 1;
offset+= digit_value;
}
}
next+= offset;
return next;
}
int advance_to_next_zero_decimal()
{
assert((next % 10)!=0);
assert(digits[0]==(next % 10));
int offset= 10 - digits[0];
digits[0]+= offset;
assert(digits[0]==10);
// propagate carries forward
for (int digit_index= 0; digits[digit_index]==10 && digit_index<digit_count; ++digit_index)
{
digits[digit_index]= 0;
digits[digit_index + 1]+= 1;
max_set_digit_index= max(digit_index + 1, max_set_digit_index);
}
next+= offset;
return next;
}
private:
int next;
static const size_t digit_count= 10; // log10(2**31)
int max_set_digit_index;
int digits[digit_count];
};
Qu'est-ce que le code ci-dessus est fait itérer sur chaque gamme de nombres tels que la gamme ne contient que des nombres sans zéros. Il fonctionne en déterminant comment passer d'N000 ... à N111 ... et de N111 ... à (N + 1) 000 ..., portant (N + 1) en 1 (0) 000 ... si nécessaire.
Sur mon portable, je peux générer le nombre harmonique de 2 ^ 31 -. 1 en 8.73226 secondes
public class SumOfReciprocalWithoutZero {
public static void main(String[] args) {
int maxSize=Integer.MAX_VALUE/10;
long time=-System.currentTimeMillis();
BitSet b=new BitSet(maxSize);
setNumbersWithZeros(10,maxSize,b);
double sum=0.0;
for(int i=1;i<maxSize;i++)
{
if(!b.get(i))
{
sum+=1.0d/(double)i;
}
}
time+=System.currentTimeMillis();
System.out.println("Total: "+sum+"\nTimeTaken : "+time+" ms");
}
static void setNumbersWithZeros(int srt,int end,BitSet b)
{
for(int j=srt;j<end;j*=10)
{
for(int i=1;i<=10;i++)
{
int num=j*i;
b.set(num);
}
if(j>=100)
setInbetween(j, b);
}
}
static void setInbetween(int strt,BitSet b)
{
int bitToSet;
bitToSet=strt;
for(int i=1;i<=10;i++)
{
int nxtInt=-1;
while((nxtInt=b.nextSetBit(nxtInt+1))!=strt)
{
b.set(bitToSet+nxtInt);
}
nxtInt=-1;
int lim=strt/10;
while((nxtInt=b.nextClearBit(nxtInt+1))<lim)
{
b.set(bitToSet+nxtInt);
}
bitToSet=strt*i;
}
}
}
Ceci est une mise en œuvre à l'aide BitSet.I calculé la somme de tous réciproques pour entier est dans la gamme somme (1-Integer.MAX_VALUE/10).The vient jusqu'à 13.722766931560747.This est le maximum que je pouvais calculer selon BitSet depuis la plage maximale pour BitSet est Integer.MAX_VALUE.I nécessité de diviser par 10 et de limiter la plage pour éviter overflow.But il y a une amélioration significative speed.I'm juste poster ce code dans le cas où il pourrait vous donner une idée nouvelle pour améliorer votre code. (Augmentez votre mémoire à l'aide l'argument VM -Xmx[Size>350]m)
Sortie:
Total: 13.722766931560747
TimeTaken : 60382 ms
Mise à jour:
Java Porting d'une précédente réponse supprimé:
public static void main(String[] args) {
long current =11;
double tot=1 + 1.0/2 + 1.0/3 + 1.0/4 + 1.0/5 + 1.0/6 + 1.0/7 + 1.0/8 + 1.0/9;
long i=0;
while(true)
{
current=next_current(current);
if(i%10000!=0)
System.out.println(i+" "+current+" "+tot);
for(int j=0;j<9;j++)
{
tot+=(1.0/current + 1.0/(current + 1) + 1.0/(current + 2) + 1.0/(current + 3) + 1.0/(current + 4) +
1.0/(current + 5) + 1.0/(current + 6) + 1.0/(current + 7) + 1.0/(current + 8));
current += 10;
}
i++;
}
}
static long next_current(long n){
long m=(long)Math.pow(10,(int)Math.log10(n));
boolean found_zero=false;
while(m>=1)
{
if(found_zero)
n+=m;
else if((n/m)%10==0)
{
n=n-(n%m)+m;
found_zero=true;
}
m=m/10;
}
return n;
}
