# Kann man hier noch was rausholen?



## MPW (15. Dez 2005)

Moin zusammen,

ich habe heute morgen mit einem meiner Lehrer über das mathematische Problem zwei Zahlen zu finden, deren Summe der beiden Quersummen ein vielfaches von 2006 ist, da dies eine Aufgabe für die diesjährige Mathematikolympiade ist.

Er sagte mir, dass er die Aufgabe gelöst habe - auf herkömmlichen Wege - und ich sagte, da er auch recht Computerinteressiert ist - warum er nicht einfach ein Programm geschrieben habe.
Wir überlegten uns dann, das dies doch recht lange dauern könnte.

Ich entschloss mich also mal kurz so'n Programm zu machen et voilà:


```
import java.math.BigInteger;

class Problem2006 implements Runnable {
	BigInteger a;
	BigInteger b;
	boolean notready = true;
	BigInteger eins = new BigInteger("1");

	public Problem2006(int zahl) {
		System.out.println("Zunächst wird die kleinstmögliche Zahl"+
"bestimmt, um die Rechenzeit zu verkürzen.");
		int k = zahl/2-1;
		int st = k/9;
		String start = "";
		for (int i = 0; i < st; i++) {
			start += "9";
		}
		System.out.println("Die kleinstmögliche Zahl ist " + start + ".");
		a= new BigInteger(start);
		b = new BigInteger(a.add(eins).toString());
		System.out.println("Beginn des Rechenvorgangs. Es wird einmal"+
"pro Minute eine Angabe über die aktuell berechneten Zahlen gemacht.");
		new Thread(this).start();
		while ((quersumme(a) + quersumme(b))%zahl != 0) {
			a = a.add(eins);
			b = b.add(eins);
		}
		System.out.println("Das kleinste Zahlenpaar, was die Bedinngungen erfüllt, wurde gefunden:");
		System.out.println("Es sind die Zahlen " + a.toString() + " und " + b.toString() + ",");
		System.out.println("denn die Summe der beiden Quersummen beträgt " + (quersumme(a) + quersumme(b)) + ",");
		System.out.println("was " + (quersumme(a) + quersumme(b))/zahl + " mal " + zahl + " ist.");
		notready = false;
	}
	long quersumme(BigInteger bi) {
		String s = bi.toString();
		long r = 0;
		char c[] = s.toCharArray();
		for (char b : c) {
			r += Integer.parseInt(Character.toString(b));
		}
		return r;
	}
	public static void main(String args[]) {
		try {
			int number = Integer.parseInt(args[0]);
			long s = System.currentTimeMillis();
			new Problem2006(number);
			long s2 = System.currentTimeMillis();
			long t = s2-s;
			long sus;
			String time = "";
			sus = t/1000/60/60/24;
			time += sus + " d ";
			t -= sus*1000*60*60*24;
			sus = t/1000/60/60;
			time += sus + " h ";
			t -= sus*1000*60*60;
			sus = t/1000/60;
			time += sus + " min ";
			t -= sus*1000*60;
			sus = t/1000;
			time += sus + " s ";
			t -= sus*1000;
			time += t + " ms";
		System.out.println("Der Rechenvorgang hat " + time + " gedauert.");
		} catch (NumberFormatException e) {
			System.out.println("Die von Ihnen angegebene Zahl ist ungültig.");
		} catch (ArrayIndexOutOfBoundsException e) {
			System.out.println("Es wurde keine Zahl angegeben.");
		}
	}
	public void run() {
		while (notready) {
			System.out.println("Der Computer ist gerade bei den Zahlen " + a.toString() + " und n+1.");
			System.out.println("");
			System.out.println("");
			try {
				for (int i = 0; i < 60; i++) {
					Thread.sleep(1000);
					if (notready == false) {
						break;
					}
				}
			} catch (InterruptedException e) {
			}
		}
	}
}
```

Es funktioniert für kleine Zahlen, läuft aber bei großen sehr lange.

Ich frage mich, ob man jetzt noch Optimierungen, *und zwar nur Java-technischer, nicht algorythmischer Seite* vornehmen könnte.
Mir ist schon klar, dass es mit einem besseren Algorithmus schneller geht, aber wir wollen ja die minimale Zeit, die ein Rechner bei stumpfen ausprobieren braucht, ermitteln.

Die Hauptrechenzeit wird natürlich in der Schleife des Konstruktors und in der Methode quersumme verbracht.
Kann man da noch was optimieren?

Man könnte natürlich noch den Thread abschalten, aber ich möchte immer mal gerne zwischen durch wissen, wie weit er ist...

Wenn noch jemannd Ideen hat, wäre ich dankbar.

MfG
MPW

[edit:] Ich nehme nicht an dem Wettbewerb teil, nicht, dass da einer glauben würde, er würde mir helfen. Nebenbeigesagt hätten wir ja schon - wie oben beschrieben - eine Lösung. Es ist eine reine Interessenssache.


----------



## Beni (15. Dez 2005)

Ich denke hier...

```
for (char b : c) {
         r += Integer.parseInt(Character.toString(b));
      }
```
...könntest du noch Performance gewinnen: Der _char b_ kann nur eines von '0', '1', ... '9' sein, mit einem switch-case-Statement kannst du direkt darauf reagieren (ist übrigens auch schneller als 10 verschachtelte if-else...). Derzeit erstellst du bei jedem Durchlauf einen neuen String, was nicht eben performant ist. Das "parseInt" ist auf alle möglichen Eingaben ausgelegt, und macht vielmehr Überprüfungen als in diesem speziellen Fall notwendig wären.


----------



## Murray (15. Dez 2005)

Wenn man sich Tatsache zunutze macht, dass die Character '0'-'9' den ASCII-Codes 48-57 entsprechend, geht es noch einfacher:

```
public static int quersumme( BigInteger big) {
		int res = 0;
		byte[] ba = (big.toString()).getBytes();
		for ( byte b : ba) res += (b-48); //--- '0'..''9' = ASCII-Codes 48..57
		
		return res;

	}
```


----------



## Roar (15. Dez 2005)

oder einfach r+= b - 48;
is bestimmt noch schneller 
noch schneller wärs bestimmt einfach longValue() von BigInteger zu benutzen und mit der zahl dann die quersumme zu berechnen statt dem gefummel mit den strings. (das gilt übrigens auch für andere stellen  ). hast du dir denn mal angeguckt wo die meiste zeit verbraten wird?


----------



## MPW (15. Dez 2005)

Hm, danke für die Antworten.

Also ich weiß ja grob wo die meiste Zeit verbracht wird,

da die Schleife nur aus 2 Anweisungen besteht, die man meiner Meinung nach nicht mehr schneller machen kann(oder gibt es ein inkrement für BigInteger(als methode)). Ich hab' jedenfalls keines gefunden in der API, villt, war ich ja bloß wieder zu blind, aber ich merke auch ganz deutlich, dass diese BigInteger zwar in der Theorie ganz toll sind, praktisch aber zu langsam.(nichts gegen Java, das ist technisch einfach nicht machbar, da die Zahlensummen bei 100-stelligen Zahlen einfach gigantisch sind.)

somit bleibt ja nur diese Quersummenmethode.
Meint ihr die Zeit des Sprunges zwischen Methode und Schleife sollte man abschaffen, in dem man den Code oben reinkopiert?

ich werd' das von da oben mal umsetzen.

Das Problem ist aber, selbst wenn ich 50% rausholen würde, würde es immer noch zu lange dauern, ich muss auch vom Alogorithmus her noch was umstellen, zu Zeit schafft er nämlich gerade mal 9 Millionen Zahlenpaare pro Minute, selbst wenn ich das verdopple sitzt der da Monate, wenn nicht Jahre dran.
Ich muss die zu prüfenden Zahlen noch irgendwie eingrentzen, und zwar deutlich.

Ich hab' mir mal überlegt, dass es eigentlich immer bei einem 10er Sprung nur sein kann, d.h. ich brächte nur die Zahlenpaar mti 9 und 0 hinten untersuchen, oder?


----------



## Mag1c (16. Dez 2005)

Hi,

hab ich das in der Aufgabe übersehen ? Sollen die zwei Zahlen aufeinanderfolgend sein ?

Wenn dem so ist, muß die kleinere der beiden immer auf 9 enden. Andernfalls ist die Summe der Quersummen immer ungerade.

Gruß
Mag1c


----------



## Mag1c (16. Dez 2005)

Ich nochmal,

warum willst du denn unbedingt ALLE Zahlen testen ?

Hiermit:


```
a = new BigInteger("9");
      b = new BigInteger(a.add(eins).toString());
      step = new BigInteger("10");
      int d = 8;
      System.out.println("Beginn des Rechenvorgangs. Es wird einmal"+
"pro Minute eine Angabe über die aktuell berechneten Zahlen gemacht.");
      new Thread(this).start();
      while ((quersumme(a) + quersumme(b))%zahl != 0) {
         a = a.add(step);
         b = b.add(step);
         if (--d == 0) {
        	 step = step.multiply(zehn);
        	 d = 9;
         }
      }
```

habe ich nach 163 ms ein Ergebnis  Es müsste sogar das kleinste Zahlen-Paar herauskommen.

Gruß
Mag1c


----------



## Guest (16. Dez 2005)

Noch ein kleiner Änderungsvorschlag.
Das hier
	
	
	
	





```
int st = k/9; 
String start = ""; 
for (int i = 0; i < st; i++) { 
  start += "9"; 
}
```
in das hier ändern
	
	
	
	





```
int st = k/9; 
StringBuilder sb = new StringBuilder(st);
for (int i = 0; i < st; i++) { 
  sb.append("9"); 
}
String start = sb.toString();
```


----------



## Bleiglanz (16. Dez 2005)

```
b = new BigInteger(a.add(eins).toString())
```
zwar nur einmal aber unschön

ich würd mal über folgendes nachdenken: b brauchst du gar nicht mitzuschleppen, das ist eh immer a+1

also braucht man eine schnelle methode für 

quersumme(a) + quersumme(a+1)

immer wenn die letzte ziffer von a=0,....,8 ist, dann ist das

2 * quersumme(a) +1

nur im fall dass die letzte ziffer 9 ist, muss man a+1 ausrechnen


```
long quersummeVonNundNplus1(BigInteger n){
        long result = 0;
        char[] digits = n.toString(10).toCharArray();
        int length = digits.length;
        for(int i=0;i<length;i++){
            result += digits[i]-48; 
        }
        if('9'==digits[length-1]){
            char[] nextdigits = n.add(BigInteger.ONE).toString(10).toCharArray();
            int nextlength = nextdigits.length;
            for(int i=0;i<nextlength;i++){
                result += nextdigits[i]-48; 
            }            
        }else{
            result = 2*result +1;
        }
        return result;
    }
```


----------



## Bleiglanz (16. Dez 2005)

hm, die kleinste Zahl zum Anfangen ist

999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

dann zählt er eins dazu

1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

und fängt da an hochzuzählen mit +1, leider ist die Quersumme erst mal kümmerliche 1 und die wird auch nicht so schnell grösser :-(

so geht das wahrscheinlich nicht, wenn die Lösung wie ich vermute 

899999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

ist (8 gefolgt von 221 Neunen)


----------



## MPW (16. Dez 2005)

Moin zusammen,

also erstmal vielen vielen Dank, für die vielen Antworten, ich hab' mal einiges umgesetztsiehe unten)

Aber mal zu euren Überlegungen:

@Murray: hab' ich übernommen

@Roar, das mit dem r+=b-48 hat Murray doch, das mit dem longValue() ist ganz nett, geht aber nicht mehr bei 400-stelligen Zahlen

@Mag1c: ja, die Zahlen müssen aufeinander folgend sein. Deine Idee mit dem 9 und 0 ist aber nur teilweise richtig, nur wenn die zahl = gerade, bei ungerade kommen immer die Zahlen 8 und 9.
Habe das aber entsprechend eingebaut mit einer If-Anweisung, siehe unten.
Ich teste jetzt auch nurnoch die Zahlen, die überhaupt in Frage kommen können. aber 163 ms ist schlichtweg ein unmögliches Ergebnis, für welche Zahl denn? bei 206 rechnet der immer ncoh lange, bei 2006 wahrscheinlich noch viel länger....

@Gast
Hab' ich übernommen. Danke

@Bleiglanz, die Überlegungen kann ich nicht nachvollziehen? aber ich hab' so das Gefühl, dass du dir selber nicht so ganz sicher bist.


```
import java.math.BigInteger;

class Problem2006 implements Runnable {
	BigInteger a;
	BigInteger b;
	boolean notready = true;
	BigInteger step = new BigInteger("10");
	BigInteger eins = new BigInteger("1");

	public Problem2006(int zahl) {
		System.out.println("Zunächst wird die kleinstmögliche Zahl bestimmt, um die Rechenzeit zu verkürzen.");
		int k = zahl/2-1;
		int st = k/9;
		StringBuilder sb = new StringBuilder(st);
		for (int i = 0; i < st; i++) {
			sb.append("9");
		}
		String start = sb.toString();
		System.out.println("Die kleinstmögliche Zahl ist " + start + ".");
		a = new BigInteger(start);
		if (zahl%2 == 0) {
			b = new BigInteger(a.add(eins).toString());
		} else {
			b = new BigInteger(a.subtract(eins).toString());
		}
		System.out.println("Beginn des Rechenvorgangs. Es wird einmal pro Minute eine Angabe über die aktuell berechneten Zahlen gemacht.");
		new Thread(this).start();
		while ((quersumme(a) + quersumme(b))%zahl != 0) {
			a = a.add(step);
			b = b.add(step);
		}
		System.out.println("Das kleinste Zahlenpaar, was die Bedinngungen erfüllt, wurde gefunden:");
		System.out.println("Es sind die Zahlen " + a.toString() + " und " + b.toString() + ",");
		System.out.println("denn die Summe der beiden Quersummen beträgt " + (quersumme(a) + quersumme(b)) + ",");
		System.out.println("was " + (quersumme(a) + quersumme(b))/zahl + " mal " + zahl + " ist.");
		notready = false;
	}
	int quersumme(BigInteger big) {
		int res = 0;
		byte[] ba = (big.toString()).getBytes();
		for ( byte b : ba) res += (b-48); //--- '0'..''9' = ASCII-Codes 48..57
		return res;
	}
	public static void main(String args[]) {
		try {
			int number = Integer.parseInt(args[0]);
			long s = System.currentTimeMillis();
			new Problem2006(number);
			long s2 = System.currentTimeMillis();
			long t = s2-s;
			long sus;
			String time = "";
			sus = t/1000/60/60/24;
			time += sus + " d ";
			t -= sus*1000*60*60*24;
			sus = t/1000/60/60;
			time += sus + " h ";
			t -= sus*1000*60*60;
			sus = t/1000/60;
			time += sus + " min ";
			t -= sus*1000*60;
			sus = t/1000;
			time += sus + " s ";
			t -= sus*1000;
			time += t + " ms";
		System.out.println("Der Rechenvorgang hat " + time + " gedauert.");
		} catch (NumberFormatException e) {
			System.out.println("Die von Ihnen angegebene Zahl ist ungültig.");
		} catch (ArrayIndexOutOfBoundsException e) {
			System.out.println("Es wurde keine Zahl angegeben.");
		}
	}
	public void run() {
		while (notready) {
			System.out.println("Der Computer ist gerade bei den Zahlen " + a.toString() + " und n+1.");
			System.out.println("");
			System.out.println("");
			try {
				for (int i = 0; i < 60; i++) {
					Thread.sleep(1000);
					if (notready == false) {
						break;
					}
				}
			} catch (InterruptedException e) {
			}
		}
	}
}
```

Also nochmal vielen Dank an alle, ich bin mal gespannt, ob ich so innerhalb der Lebensdauer eines Computers zu einem Ergebnis komme.
Aber wenn noch jemannd eine Idee hat, raus damit.


----------



## Murray (16. Dez 2005)

Vielleicht könnte man hier noch etwas rausholen:

```
while ((quersumme(a) + quersumme(b))%zahl != 0) {
         a = a.add(step);
         b = b.add(step);
      }
```

Hier wird ja von den BigIntegers nur die Quersumme gebildet und 10 addiert. Das kann man auch mit Strings nachbilden. Die Methode quersumme() bildet intern sowieso die String-Repräsentation, und die Addition von 10 kann man auch relativ einfach nachbilden: Wert der vorletzen Stelle um 1 erhöhen. Wenn neuer Wert < 10, dann ist man bereits fertig, sonst muss man die nächsthöhere Stelle umf 1 erhöhen u.s.w.

Ob das schneller ist als die Verwendung von BigIntegers wäre auszuprobieren.

Dann könnte man auch noch anstelle von Strings direkt auf byte[] setzen; dadurch würde man jede Menge Objeketrzeugungen sparen, hätte sich aber eben selbst um die Verwlatung zu kümmern.


----------



## Mag1c (16. Dez 2005)

Hi,

probiere es doch aus, habe den Code oben gepostet. Und ich habe nach 2006 gesucht, so wie es die Aufgabe vorgibt.
Hier mal die Ausgabe (hab sie noch etwas modifiziert, wegen der langen Zahlen)


```
Das kleinste Zahlenpaar, was die Bedinngungen erfüllt, wurde gefunden:
Es sind die Zahlen 
  9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999989 (112 Stellen)
  9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999990 (112 Stellen)
denn die Summe der beiden Quersummen beträgt 2006,
was 1 mal 2006 ist.
Der Rechenvorgang hat 0 d 0 h 0 min 0 s 205 ms gedauert.
```

Die Summe der Quersummen kann man im Kopf ausrechnen (falls man dem Programm nicht traut  ):

2 * (110 * 9) + 8 + 9 + 9 + 0 = 2006

EDIT: da ich von 2006 ausgegangen bin, funktioniert mein Code oben natürlich nicht mit ungeraden Zahlen.

Gruß
Mag1c


----------



## MPW (16. Dez 2005)

Also entweder hab' ich dich falsch verstanden, oder wir reden aneinander vorbei......

Wenn du manuell eine Startzahl gibst, wo nur noch 1 fehlt, ist mir klar, dass es nur xx ms braucht, aber ich brauche ja dann einen Algorithmus um die Startzahl zu verwenden, kann ja nicht jedesmal das Programm umschreiben....


----------



## Mag1c (16. Dez 2005)

Hi,

also zahl ist wie aus der Aufgabenstellung 2006.
Anfangen tue ich mit *a = 9* und *b = a +1 = 10*

Der Trick ist, daß ich nicht einfach die Zahlen erhöhe, so wie du es versuchst.
Ich erhöhe eine Zehnerstelle bis 9 und mache dann mit der nächsten Zehnerstelle weiter.
Mit der zweiten Zehnerstelle fange ich an (deswegen ist *step = 10*) und bei dieser darf
ich nur bis 8 zählen, da ja bei der Zahl b von der niedrigsten Stelle ein Übertrag kommt.

die getesteten Zahlenpaare sind dann etwa:

9/10, 19/20, 29/30, 39/40, ..., 89/90 - jetzt fertig mit der 2. Stelle, daher wird step = step * 10 = 100

189/190, 289,290, 389/390, ..., 989/990 - fertig mit 3. Stelle; step = step * 10 = 1000

1989/1990, 2989/2990,...

usw. bis zum Ergebnis.

Gruß
Mag1c


----------



## Guest (19. Dez 2005)

Interessantes Problem. 
Ohne jetzt den Algorithmus zu zerpflücken, du kanns es um einiges Beschleunigen, wenn 
du weniger Strings produzierst. 
z.B. Parameter 120 auf enem ziemlich langsamen PC
Deine Version: 19s 859 ms
Meine Version: 219 ms

```
class Problem2006 implements Runnable
{
   BigNumber a;
   BigNumber b;
   boolean notready = true;

   public Problem2006(int zahl) {
      System.out.println("Zunächst wird die kleinstmögliche Zahl bestimmt, um die Rechenzeit zu verkürzen.");
      int k = zahl/2-1;
      int st = k/9;
      StringBuilder sb = new StringBuilder(st);
      for (int i = 0; i < st; i++) {
         sb.append("9");
      }
      String start = sb.toString();
      System.out.println("Die kleinstmögliche Zahl ist " + start + ".");
      BigInteger tmpA = new BigInteger(start);
      BigInteger tmpB;
      if (zahl%2 == 0) {
         tmpB = new BigInteger(tmpA.add(new BigInteger("1")).toString());
      } else {
         tmpB = new BigInteger(tmpA.subtract(new BigInteger("1")).toString());
      }
      a = new BigNumber(tmpA.toString());
      b = new BigNumber(tmpB.toString());
      System.out.println("Beginn des Rechenvorgangs. Es wird einmal pro Minute eine Angabe über die aktuell berechneten Zahlen gemacht.");
      new Thread(this).start();
      while ((a.qsum() + b.qsum())%zahl != 0) {
         a.inc();
         b.inc();
      }
      System.out.println("Das kleinste Zahlenpaar, was die Bedinngungen erfüllt, wurde gefunden:");
      System.out.println("Es sind die Zahlen " + a.toString() + " und " + b.toString() + ",");
      System.out.println("denn die Summe der beiden Quersummen beträgt " + (a.qsum() + b.qsum()) + ",");
      System.out.println("was " + (a.qsum() + b.qsum())/zahl + " mal " + zahl + " ist.");
      notready = false;
   }

   public static void main(String args[]) {
      try {
         int number = Integer.parseInt(args[0]);
         long s = System.currentTimeMillis();
         new Problem2006(number);
         long s2 = System.currentTimeMillis();
         long t = s2-s;
         long sus;
         String time = "";
         sus = t/1000/60/60/24;
         time += sus + " d ";
         t -= sus*1000*60*60*24;
         sus = t/1000/60/60;
         time += sus + " h ";
         t -= sus*1000*60*60;
         sus = t/1000/60;
         time += sus + " min ";
         t -= sus*1000*60;
         sus = t/1000;
         time += sus + " s ";
         t -= sus*1000;
         time += t + " ms";
      System.out.println("Der Rechenvorgang hat " + time + " gedauert.");
      } catch (NumberFormatException e) {
         System.out.println("Die von Ihnen angegebene Zahl ist ungültig.");
      } catch (ArrayIndexOutOfBoundsException e) {
         System.out.println("Es wurde keine Zahl angegeben.");
      }
   }
   public void run() {
      while (notready) {
         System.out.println("Der Computer ist gerade bei den Zahlen " + a.toString() + " und n+1.");
         System.out.println("");
         System.out.println("");
         try {
            for (int i = 0; i < 60; i++) {
               Thread.sleep(1000);
               if (notready == false) {
                  break;
               }
            }
         } catch (InterruptedException e) {
         }
      }
   }
}

public class BigNumber
{
  // Puffer für die grosse Zahl
  int digits[];
  // Aktuelle Quersumme
  int qsum=0;
  // Größe der Zahl
  int size;
  // Offset der Zahl im Puffer
  int digitsOffset;

  public BigNumber(String s)
  {
    size = s.length();
    resize(size*2);
    // Die Zahl in den Puffer kopieren
    // und gleichzeitig die Quersumme berechnen
    for(int i=s.length()-1, j=digits.length-1; i>=0; i--, j--)
    {
      digits[j] = s.charAt(i)-48;
      qsum += digits[j];
    }
    digitsOffset = digits.length - size;
  }

  private void resize(int n)
  {
    int tmp[] = digits;
    digits = new int[n];
    if(tmp!=null)
      System.arraycopy(tmp, 0, digits, digits.length-tmp.length, tmp.length);
  }

  public int qsum()
  {
    // Quersumme wird immer beim Inkrementieren berechnet
    return qsum;
  }

  public void inc()
  {
    int currentOffset = digits.length-2; // Letzte Stelle wird ignoriert (inc in 10er Schritten)
    if(digits[currentOffset]==9) // Aktuelle 10er Stelle ist 9?
    {
      int n=0;
      // Solange aktuelle Stelle 9 ist, jeweils um eine Position nach rechts gehen
      // z.B. 1299995 wird dadurch zu 1200005 (später wird die 2 inkrementiert)
      do 
      {
        digits[currentOffset--] = 0; // die 9 durch 0 ersetzen
        n++;
      }
      while(currentOffset>=digitsOffset && digits[currentOffset]==9);

      qsum -= n*9; // Die auf 0 gesetzten 9er von der Quersumme abziehen
      
      // Zahl ist um eine Stelle größer geworden?
      if(currentOffset<digitsOffset)
      {
        size++;
        // Wenn Zahl größer als der Puffer, dann Puffergröße verdoppeln 
        if(size>digits.length)
          resize(size*2);
        // und den Offset innerhalb des Puffers (wo die ZAhl anfängt) wieder anpassen
        currentOffset = digits.length-size;
        digitsOffset = currentOffset;
      }
    }
    // Die Zahl und die Quersumme inkrementieren
    digits[currentOffset]++;
    qsum++;
  }

  public String toString()
  {
    StringBuilder s = new StringBuilder(digits.length);
    for(int i=digitsOffset; i<digits.length; i++)
      s.append((char)(digits[i]+48));
    return s.toString();
  }
}
```


----------



## Bleiglanz (19. Dez 2005)

ich meinte folgendes

wenn du mit 999999999 anfängst, dann springt das nach

1000000000

und dann fängst du an zu iterieren

1000000001
1000000002
1000000003
1000000004
...

aber diese Zahlen haben alle eine viel zu kleine Quersumme, das wird zu deinen Lebzeiten nicht zu einem Ergebnis kommen

Übrigens ist Quersumme(a)+Quersumme(b) das gleiche wie

2 * Quersumme(a) + 1 - 9 * (Anzahl der 9en am Ende)


----------

