Java: A fractal algorithm shows prime number patterning

Question

The fully working example finds all primes (theoretically). In real life the FA is constrained by stack size. The theoretical run is important, because it proves that all primes have a deterministic distribution. See videos on https://www.youtube.com/watch?v=I0w78ewvum4 https://youtu.be/2W1oi7g1rdE

The code can be also found on github. https://github.com/cerebrummi/fractalalgorithm

It implements SFA with FA from my paper: https://zenodo.org/records/16829092

package common;

public class StartFA
{
   public static void main(String[] args)
   {
      SFA sfa = new SFA();
      
      for( int i = 0 ; i < 8; i++)
      {
         sfa.step();
      }
   }
}

AND

package common;

import fa.walksets.APn;
import fa.walksets.An;
import fa.walksets.BPn;
import fa.walksets.Bn;
import fa.walksets.CPn;
import fa.walksets.Cn;

public class SFA
{
   // production line one
   An walksetAn = new An();
   Bn walksetBn = new Bn();
   Cn walksetCn = new Cn();

   // production line two
   APn walksetAPn = new APn();
   BPn walksetBPn = new BPn();
   CPn walksetCPn = new CPn();

   public SFA()
   {
      // starting state
      checkStartingState();
      printWalksets();
   }
   

   public void step()
   {
      System.out.println("========== step start ==========");
      // update walkset An
      if(walksetBn.getN()!= null)
      {
         walksetAn.addElement(walksetBn.cutN());
      }
      
      // update walkset Bn
      walksetBn.setN(walksetCn.cutLeftmostElement());
      
      // update walkset Cn
      // has already taken place during update Bn
      
      // update walkset APn
      if(walksetBPn.getN()!= null)
      {
         walksetAPn.addElement(walksetBPn.cutN());
      }
      
      // update walksetBPn
      walksetBPn.setN(walksetCPn.getLeftmostElement());
      
      // find wether n in Bn is prime
      if(walksetBn.getN() == 1)
      {
         walksetBPn.setN("1");
      }
      else
      {
         if(walksetBPn.getN().equals("L"))
         {
            walksetBPn.setN("P");
         }
      }
      
      // update walksetCPn
      walksetCPn.move();
      if(walksetBPn.getN().equals("P"))
      {
         walksetCPn.copy(walksetBn.getN());
         walksetCPn.change(walksetBn.getN());
      }
      
      printWalksets();
      System.out.println("========== step end ===========");
   }

   private void printWalksets()
   {
      walksetAn.print();
      walksetAPn.print();
      
      walksetBn.print();
      walksetBPn.print();
      
      walksetCn.print();
      walksetCPn.print();
   }


   private boolean checkStartingState()
   {
      if(!walksetAn.getList().isEmpty())
      {
         System.out.println("Error in starting state of An");
         return false;
      }
      
      if(walksetBn.cutN()!= null)
      {
         System.out.println("Error in starting state of Bn");
         return false;
      }
      
      if(walksetCn.getLeftmostElement() != 1)
      {
         System.out.println("Error in starting state of Cn");
         return false;
      }

      if(!walksetAPn.getList().isEmpty())
      {
         System.out.println("Error in starting state of APn");
         return false;
      }
      
      if(walksetBPn.getN()!= null)
      {
         System.out.println("Error in starting state of BPn");
         return false;
      }
      
      if(!walksetCPn.getLeftmostElement().equals("L"))
      {
         System.out.println("Error in starting state of CPn");
         return false;
      }
      
      return true;
   }

}

AND

package fa.walksets;

public interface walkset
{
   public void print();
}

AND

package fa.walksets;

import java.util.ArrayList;
import java.util.StringJoiner;

public class An implements walkset
{
   ArrayList<Integer> list = new ArrayList<>();

   public void addElement(int n)
   {
      list.add(n);
   }

   public ArrayList<Integer> getList()
   {
      return list;
   }

   @Override
   public void print()
   {
      String start = "An < ";
      StringJoiner joiner = new StringJoiner(",");
      for (int element : list)
      {
         joiner.add(String.valueOf(element));
      }
      String end = " >";
      System.out.println(start + joiner.toString() + end);
   }
}

AND

package fa.walksets;

import java.util.ArrayList;
import java.util.StringJoiner;

public class APn implements walkset
{
   ArrayList<String> list = new ArrayList<>();

   public void addElement(String n)
   {
      list.add(n);
   }

   public ArrayList<String> getList()
   {
      return list;
   }

   @Override
   public void print()
   {
      String start = "APn < ";
      StringJoiner joiner = new StringJoiner(",");
      for (String element : list)
      {
         joiner.add(String.valueOf(element));
      }
      String end = " >";
      System.out.println(start + joiner.toString() + end);
   }
}

AND

package fa.walksets;

public class Bn implements walkset
{
   Integer n;

   public Integer cutN()
   {
      Integer copyOfN = n;
      n = null;
      return copyOfN;
   }

   public Integer getN()
   {
      return n;
   }

   public void setN(int n)
   {
      this.n = n;
   }

   @Override
   public void print()
   {
      System.out.println("Bn = < " + n + " >");
   }
}

AND

package fa.walksets;

public class BPn implements walkset
{
   String n;

   public String getN()
   {
      return n;
   }

   public void setN(String n)
   {
      this.n = n;
   }

   public String cutN()
   {
      String copyOfN = n;
      n = null;
      return copyOfN;
   }

   @Override
   public void print()
   {
      System.out.println("BPn = < " + n + " >");
   }
}

AND

package fa.walksets;

public class Cn implements walkset
{
   int leftmostElement = 1;

   public int cutLeftmostElement()
   {
      return leftmostElement++;
   }
   
   public int getLeftmostElement()
   {
      return leftmostElement;
   }

   @Override
   public void print()
   {
      System.out.println("Cn = < " + leftmostElement + ", ... infinity >");
   }
}

AND

package fa.walksets;

import java.util.Arrays;
import java.util.LinkedList;

public class CPn implements walkset
{
   LinkedList<String> list = new LinkedList<>();
   
   public CPn()
   {
      list.add("L");
   }
   
   public void move()
   {
      String element = list.pollFirst();
      list.add(element);
   }
   
   public void copy(int n)
   {
      LinkedList<String> copiedList = new LinkedList<>();
      
      for(int i = 0; i < n; i++)
      {
         for(String element : list)
         {
            copiedList.add(element);
         }
      }
      
      list = copiedList;
   }
   
   public void change(int n)
   {
      LinkedList<String> copy = new LinkedList<>();
      for(String element: list)
      {
         copy.add(element);
      }
      int index = 1;
      for(int i = 0; i < copy.size(); i++)
      {
         if(index%n==0 && list.get(i).equals("L"))
         {
            list.set(i, "M");
         }
         index++;
      }
   }
   
   public String getLeftmostElement()
   {
      return list.getFirst();
   }

   @Override
   public void print()
   {
      System.out.println("CPn = < " + Arrays.toString(list.toArray()) + " >");
   }
}

Maarten Bodewes · Accepted Answer · 2025-08-14 18:25:05Z

Cool project. Three changes will make the Java side safer and easier to reason about.

checkStartingState mutates state while “checking” checkStartingState() calls walksetBn.cutN() which clears Bn.n. A check should not change program state. Use a getter instead and keep checks side‑effect free.

private boolean checkStartingState() {
    if (!walksetAn.getList().isEmpty()) {
        System.out.println("Error in starting state of An");
        return false;
    }
    // do not call cutN() here
    if (walksetBn.getN() != null) {
        System.out.println("Error in starting state of Bn");
        return false;
    }
    // rest unchanged...
    return true;
}

Replace magic strings and nulls with a proper model Right now "L", "M", "P", and "1" live as raw Strings across BPn/CPn, plus null as a state. That’s fragile and forces lots of equals(...) checks. Use an enum and ban nulls.
```
enum Mark { L, M, P }
final class BPn implements Walkset {
    private Mark mark; // never null
    public Optional<Mark> mark() { return Optional.ofNullable(mark); }
    public void setMark(Mark m) { this.mark = Objects.requireNonNull(m); }
    // print uses mark.name()
}
```
In SFA.step() prefer if (walksetBPn.mark().orElse(Mark.L) == Mark.L) { ... }. Your intent becomes obvious and you avoid NPEs.
Follow Java naming and separation of concerns
- Interface walkset should be Walkset, and fields should be private with clear accessors.
- print() in every class couples data to I/O. Prefer toString() and let SFA decide when to System.out.println. That makes the core testable.
- CPn.copy(int n) rebuilds the list in O(n × size) using LinkedList. If you need bulk replication, use ArrayList with pre‑sized capacity and Collections.nCopies or repeated addAll. move() looks like a rotate; ArrayDeque fits better than LinkedList.

This is an example of a safer copy for the last point in the list above:

public void copy(int times) {
    if (times < 1) return;
    var src = new ArrayList<>(list);           // snapshot
    var out = new ArrayList<String>(src.size() * times);
    for (int i = 0; i < times; i++) out.addAll(src);
    list = out;
}

Thank you, I adopted most of your suggestions. My goal is to keep code readable for beginners. — dragoness
– dragoness, Commented Aug 14 at 15:15
Hi Yuliia, I mainly added some spacing and such to put the code blocks etc. directly behind the text of the lists. If you want I can also put the example for copy directly under the bullet, question of adding enough spaces in front of the code block. Put an enter at the end of the three backticks of the last code block to make the backticks disappear. — Maarten Bodewes
– Maarten Bodewes, Commented Aug 14 at 18:28
@Yulia I added a video where you can see the output pattern of my previous research implementation youtube.com/watch?v=I0w78ewvum4 — dragoness
– dragoness, Commented Aug 18 at 10:24

Maarten Bodewes · Accepted Answer · 2025-08-14 19:09:27Z

Some additions to the already accepted answer:

When implementing code such as this create a JavaDoc for the package or main class that references the paper (link including title and authors in the text). Then when implementing functions etc. it would be great if you'd also include the sections that you implement for easy reference.
for( int i = 0 ; i < 8; i++) without such a reference the number 8 is a magic number. It should probably be a constant, and if it is taken from the paper, then indicate from which part (see previous item). Still make it a constant though.
checkStartingState() should probably be renamed validStartingState() as you would expect that function to return a boolean. Check is more generic and is often used for methods that generate exceptions instead. If the rest is already validated in a normal code run then this method could be implemented using assertions instead.
Don't use System.out for tracing or debugging, use a logger instead. In real settings the use of System.out for this kind of purpose is highly discouraged as a user may suddenly be presented by unexpected output. Personally I don't think checkStartingState() is necessary at all; it's only used once and only used (incorrectly as already noted) to change one variable. Most of your debugging statements are at "trace" level (the lowest possible), althouh error conditions should of course be higher.
The walker interface & implementations should not be public as they are implementation details, and they are unlikely to be required on their own. I'd simply remove public and make them the default package visible.
If you have a public class anyway then getters such as public ArrayList<String> getList() become dangerous as they return a mutable list. As it is only required for a test later on, I'd simply create a method isEmpty() instead. That way you don't expose the innards. Or, even more generically, you could each walker have an isValid method to check the inner state. That way you can keep the class specific testing together with the class.
Your copy method is basically pruning the list up to n elements. First of all, I'd always first check if n is within bounds. Then you can just remove the tail of the list.
It is entirely unclear to the unwitting developer what move and change do, you'd have to dive into the code to know what is happening in there. Maybe this is explained in the paper, but as the other answer already suggested, I'd probably rename these methods or at least point to the definition of the functions in the paper. move() I could at least figure out without visualizing the method in my head, change not so much.

The naming is of course a bit specific to the use case, but that's fine - again as long as the paper is referenced. Code is relatively clear and easy on the eyes, even if it is not strictly according to the normal conventions.

Sorry, removed one item about using int instead of an Integer. Here you need it if the integer is optional. It's not great, but neither is using Optional as field (highly discouraged) or using a magic number instead. — Maarten Bodewes
– Maarten Bodewes, Commented Aug 14 at 19:11
Thank you, I adopted most of your suggestions. My goal is to keep code readable for beginners. — dragoness
– dragoness, Commented Aug 15 at 7:54

Stack Exchange Network

Java: A fractal algorithm shows prime number patterning

2 Answers 2

You must log in to answer this question.

Linked

Hot Network Questions

Java: A fractal algorithm shows prime number patterning

2 Answers 2

You must log in to answer this question.

Linked

Related

Hot Network Questions