chotto2/amida repository overview

⁠Amida - Divisor Algorithm Based on 45-Degree Mirror Conjecture

⁠Overview

This program finds divisors of integers from 0 to 10000000 using a novel algorithm based on the "45-degree Mirror Conjecture for Divisors" and displays them with asterisks (*).
This is a derivative program originating from the previously published dstar-dev⁠.
The asterisk pattern plotted by this program (hereafter referred to as "amida") matches the pattern generated using the Sieve of Eratosthenes.
However, it does not use the Sieve of Eratosthenes but instead employs the 45-degree Mirror Conjecture for Divisors described in the dstar-dev README.
In this sense, it can be considered an alternative algorithm to the Sieve of Eratosthenes.
The algorithm itself is simple: once a divisor is determined, it tilts 45 degrees like falling dominoes, determining the next domino, and the chain reaction continues.
Through this repetition, divisors of all integers are determined without any arithmetic operations.
The dominoes can also travel backward, and divisors are determined in that case as well.
While attractive as an algorithm, it has the drawback of large memory consumption.
Due to its large file size, the result list is not included in the repository.
Please download resultam.txt from Releases⁠ and take a look.
However, the appearance is the same as dstar-dev.

⁠Features

• 🐳 Docker Support - Reproducible build environment
• 📊 Divisors up to 10000000 - Suitable size for educational and research purposes

⁠Requirements

• Docker Desktop
• Git

⁠Result File

Due to its large file size, the result file (resultam.txt) is not included in the repository.
Please download it from the Releases⁠ page on GitHub.

# Using gh CLI
gh release download --pattern "resultam.txt"

⁠Build and Run

# Clone the repository
git clone https://github.com/chotto2/amida.git
cd amida

# Build Docker image
docker build -t amida .

# Run (Usage output)
docker run -it amida amida
USAGE: amida { {-v | --version} | <n_max> [{-m | --memory}] [{-b | --benchmark}] }

  -v, --version    Show version number
  n_max            Upper limit for divisor computation (positive integer)
  -m, --memory     Show memory required for n_max and exit (no computation)
                   (takes precedence over -b if both are specified)
  -b, --benchmark  Show elapsed/user/sys time after computation


# Run (version number output)
docker run -it amida amida -v
version: 2.0.0

# Run (list output)
docker run -it amida amida 10000000

# Run (No list output + performance measurement)
docker run -it amida amida 10000000 -b
real 4.236s user 3.993s  sys 0.106s

# Run (No list output + no performance measurement + display memory usage)
docker run -it amida amida 10000000 -m
total memory = 810901468

⁠Performance

real    4.209s
user    3.963s
sys     0.139s

※Codespace: 2-Core
※No output when the '--benchmark' argument is specified
※Average of 10 measurements ※Dynamically allocate the divisor storage area (calloc)

⁠Output Example

The output result of amida is shown below.

       n:    d(n):divisors2(n, 128)
       0:10000000:******************************** ...
       1:       1:*
       2:       2:**
       3:       2:* *
       4:       3:** *
       5:       2:*   *
       6:       4:***  *
       7:       2:*     *
       8:       4:** *   *
       9:       3:* *     *
      10:       4:**  *    *
      11:       2:*         *
      12:       6:**** *     *
      13:       2:*           *
      14:       4:**    *      *
      15:       4:* * *         *
...

The first line indicates that each line of the list consists of three fields separated by ':'.
The first field, n, indicates the target integer value.
The second field, d(n), indicates the number of divisors of integer n.
The third field, divisors2(n, 128), indicates plotting asterisks (*) at divisor positions.
The positions of divisors (asterisks) are in ascending order 1, 2, 3... from the side closer to the second field.
divisors2(n, 128) limits the upper bound of divisors to 128 and displays the results with asterisks.

For example, looking at the output for integer 6:

      6:       4:***  * 

This indicates that integer 6 has 4 divisors, which are {1, 2, 3, 6}. (Positions 4 and 5 are blank)

※Integer 0 is a special case where all non-zero integers are divisors (n × 0 = 0)

⁠Main Processing Sequence

Step 1) Plot divisors of n=0

       n:    d(n):divisors2(n, 128)
       0:10000000:********************************...
       1:       0:
       2:       0:
       3:       0:
       4:       0:
       5:       0:
       6:       0:
...

Step 2) Expand divisor pattern of n=0 from n=1 at 45-degree angle

       n:    d(n):divisors2(n, 128)
       0:10000000:********************************...
       1:       1:*
       2:       1: *
       3:       1:  *
       4:       1:   *
       5:       1:    *
       6:       1:     *
...

Step 3) Expand divisor pattern of n=1 from n=2 at 45-degree angle

       n:    d(n):divisors2(n, 128)
       0:10000000:********************************...
       1:       1:*
       2:       2:**
       3:       1:  *
       4:       1:   *
       5:       1:    *
       6:       1:     *
...

Step 4) Expand divisor pattern of n=2 from n=3 at 45-degree angle

       n:    d(n):divisors2(n, 128)
       0:10000000:********************************...
       1:       1:*
       2:       2:**
       3:       2:* *
       4:       2: * *
       5:       1:    *
       6:       1:     *
...

Step 5) Expand divisor pattern of n=3 from n=4 at 45-degree angle

       n:    d(n):divisors2(n, 128)
       0:10000000:********************************...
       1:       1:*
       2:       2:**
       3:       2:* *
       4:       3:** *
       5:       1:    *
       6:       2:  *  *
...

Step 6) Expand divisor pattern of n=4 from n=5 at 45-degree angle

       n:    d(n):divisors2(n, 128)
       0:10000000:********************************...
       1:       1:*
       2:       2:**
       3:       2:* *
       4:       3:** *
       5:       2:*   *
       6:       3: **  *
...

Step 7) Expand divisor pattern of n=5 from n=6 at 45-degree angle

       n:    d(n):divisors2(n, 128)
       0:10000000:********************************...
       1:       1:*
       2:       2:**
       3:       2:* *
       4:       3:** *
       5:       2:*   *
       6:       4:***  *
...

Step 8) By repeating the above process, divisors of all integers can be found.

⁠Technical Details

• Language: C
• Build System: CMake
• Divisor Range: 0..10000000

⁠Cautions

⚠️ Important: This version is an implementation for educational and research purposes. It handles divisors up to integer 10000000, so it does not affect modern cryptographic systems (such as RSA-4096).

⁠Future Plans

• 📝 Plan to submit paper to arXiv
• 📚 Detailed theoretical background of the algorithm

⁠License

MIT License

⁠Author

N.Arai

⁠Citation

Paper in preparation. Proper citation method will be provided after publication.

⁠Related Links

• Paper: arXiv (in preparation)
• Repository: https://github.com/chotto2/amida⁠