b2 squenz

[scott84]

Hallo erstmal,

ich habe Verständnis Probleme mit der b2 squenz bzw. Mian-Chowla squenz. Muss das in Java programmieren komme jedoch nicht auf den Algorithmus.

Die Sequenz ist auf
http://mathworld.wolfram.com/B2-Sequence.html
erklärt.

1, 2, 4, 8, 13, 21

wieso ist der 6. Wert kleiner wert4 +wert5 ?

Außerdem kann ich überhaupt nicht nachvollziehen wie man auf diese Folge kommt, da der Nachfolger aus einer Summe gebildet wird (Falls ich das richtig verstanden habe).

1, 2, 4, 8, 13, 21, 31, 45, 66

Vielen Dank schon mal.

 

[scott84]

1, 2, 4, 8, 13, 21,31

wieso ist der 7. Wert kleiner wert5 +wert6 ?

sollte es eig. heißen.

 

[Flown]

Die Reihe baut sich nicht aus den Vorgängern auf sondern nimmt Zahlen in die Reihe, die die Prämisse erfüllen:

i <= j: bi + bj

Und deren Summen müssen distinkt sein.

 

[scott84]

steht ja auch auf wolfram,

jedoch verstehe ich nicht warum bei b3=8 ist das könnte ja auch 6 sein da

1 < b1 <b2 <b3 <bn

und wie kommt man denn von b6 auf b7 und von b7 auf b8 ein kleines Beispiel wäre echt sehr hilfreich

Vielen Dank

 

[Flown]

Also 6 kann schon mal nicht sein.
Summen in der Reihe (1 + 1 = 2, 1 + 2 = 3, 1 + 4 = 5, 2 + 2 = 4, 2 + 4 = 6, 4 + 4 = 8) <=> (2, 3, 4, 5, 6, 8)
6+2 würde aber 8 ergeben, was bereits in der Summenmenge vorhanden ist.
Der nächste Kandidat für a(4) wäre a(3) + 1 und würde a(3) + 1 = 5. Danach immer um 1 erhöhen und prüfen, ob die Prämissen erfüllt werden.

 

[scott84]

Danke für die Antwort, jedoch verstehe ich die Erklärung nicht.

Vor allem bei den ersten 3 Berechnungen hast du immer die 1 vorne wieso ???
Und dann nur 2 mal die 2. Wie oft würde denn die 4 kommen ???

Und wie würde ich z.B. auf b7 kommen.

 

[Flown]

int[] b2 = { 1, 2, 4, 8 };
for (int j = 0; j < b2.length - 1; j++) {
  for (int i = 0; i <= j; i++) {
  System.out.println(b2[i] + " + " + b2[j] + " = " + (b2[i] + b2[j]));
  }
}

1 + 1 = 2
1 + 2 = 3
2 + 2 = 4
1 + 4 = 5
2 + 4 = 6
4 + 4 = 8

Erklärt dir das jetzt?

Also ich kann dir jetzt nicht mehr verraten ohne jetzt gleich den Code zu präsentieren. Aber du startest jetzt ab

8 + 1

und prüfst alles, wenn es die Vorraussetzungen erfüllt gehört es in die Reihe, falls nein versuche die nächst größere Zahl (10), etc.

 

[scott84]

Die eigentliche Aufgabe ist es zu erkennen ob eine Sequenz eine b2 Sequenz ist. Die Lösung habe ich schon bevor ich die Frage gestellt habe, darum geht es mir auch gar nicht. Ich will aus reiner neugier wissen wie man eine b2 Sequenz erzeugt. Flown dein code hat mit etwas geholfen das zu verstehen jedoch nicht ganz. Weil in der 8ter Reihe keine 13 vorkommt. In der 13er gibt es zwar eine 21 (8 + 13 = 21), jedoch dann wider in der 21er keine 31 und in der 31er keine 45.

Warum Legst du ein Array an in der die Reihe schon besteht ?? Ich will sie ja eigentlich erzeugen.


Vielen Dank nochmal für die Mühe

 

[Flown]

Die Summen müssen distinct sein nicht die Elemente in der Reihe. Mit Java 8 hast du Streams, die unendlich sein können und die Reihe kann so berechnet werden.

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.PrimitiveIterator;
import java.util.Set;
import java.util.Spliterator;
import java.util.Spliterators;
import java.util.concurrent.ConcurrentHashMap;
import java.util.stream.IntStream;
import java.util.stream.StreamSupport;

public class Test {

  public static void main(String... args) {
    b2Sequence().limit(100).forEach(System.out::println);
  }

  public static IntStream b2Sequence() {
    return StreamSupport.intStream(Spliterators.spliteratorUnknownSize(new PrimitiveIterator.OfInt() {

      @Override
      public boolean hasNext() {
        return true;
      }

      private List<Integer> b2Sequence = new ArrayList<>();
      private Set<Long> b2sums = new HashSet<Long>();
      private int last = 0;

      @Override
      public int nextInt() {
        next: for (int n = last + 1;; n++) {

          Set<Long> candidateSums = Collections.newSetFromMap(new ConcurrentHashMap<>());
          b2Sequence.add(n);
          int candidate = n;
          if (b2Sequence.parallelStream().map(b2 -> (long) b2 + candidate)
              .anyMatch(sum -> b2sums.contains(sum) || !candidateSums.add(sum))) {
            b2Sequence.remove(b2Sequence.size()-1);
            continue next;
          }
          b2sums.addAll(candidateSums);
          last = n;
          return n;
        }
      }
    }, Spliterator.ORDERED), false);
  }
}

 

[scott84]

Vielen Dank für deine Mühe

Habe eben auf die schnelle jdk8 installiert und dein prog funktioniert jetzt. Kann die Reihe ohne Streams nicht programmiert werden ?

 

[Flown]

Doch kann sie mit einem Iterator. Aber der ist ja schon im Programm oben mit PrimitiveIterator.OfInt programmiert.

Damit es komplett ist hier in < JAVA 8:

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

public class Test {

   public static void main(String... args) {
     Iterator<Integer> b2 = b2Sequence();
     for (int i = 0; i < 100; i++) {
       System.out.println(b2.next());
     }
   }

   public static Iterator<Integer> b2Sequence() {
     return new Iterator<Integer>() {

       @Override
       public boolean hasNext() {
         return true;
       }

       private List<Integer> b2Sequence = new ArrayList<>();
       private Set<Long> b2sums = new HashSet<Long>();
       private int last = 0;

       @Override
       public Integer next() {
         next: for (int n = last + 1;; n++) {
           b2Sequence.add(n);
           Set<Long> candidateSums = new HashSet<Long>();
           for (int seq : b2Sequence) {
             long sum = (long) seq + (long) n;
             if (b2sums.contains(sum) || !candidateSums.add(sum)) {
               b2Sequence.remove(b2Sequence.size() - 1);
               continue next;
             }
           }
           b2sums.addAll(candidateSums);
           last = n;
           return n;
         }
       }

     };
   }
}