# Finding Triplets for n in Brainf***: An Algorithm Analysis

• Aphex_Twin
In summary, the problem is to find a triplet of natural numbers a, b, and c that satisfy the conditions n = a*b+c+5 and abs(a-b+c) is minimum, but only if n>a+b+abs(c)+5. This problem is related to an esoteric programming language called brainf***, where the goal is to efficiently write ASCII text strings using a combination of multiplication and addition. Some possible approaches to solving this problem include setting c > 0 and a < b, and then finding solutions for the equations n = ab + c, b - a = c, and ab > a + b. It is also noted that c can only equal 0 if n is a perfect square.
Aphex_Twin
Given n, can we find a triplet a, b, c that fits the following conditions:

n = a*b+c+5
abs(a-b+c) is minimum

but only if
n>a+b+abs(c)+5

Where n, a, b are naturals and c is integer.

For instance in case of n=65, I have a hunch the best choices are:
a = b = 8
c = 1

The background for this problem stems from an esoteric programming language - brainf*** ( http://en.wikipedia.org/wiki/brainf*** ). Specifically, I'm trying to find out the most efficient way of writing up ASCII text strings (numerical values between 32 and 255). You can do it either by using an n number of + signs (basically unary, where 65 would be represented by 65 times the '+' sign). The idea is that multiplying two numbers together would be a more efficient way. The code length would be exactly a+b+abs(c)+5.

Well, you don't have to get bogged down in the details of the language, but if you have an idea for an answer, algorithm or complexity analisys of the problem, you are most welcome to post it.

Unless I'm more tired than I realize, 8*8 + 1 + 5 = 70. For n = 65, I found a = 5, b = 11, c = 5 pretty quickly by just putting things together and simplifying:
1) ab + c + 5 > a + b + |c| + 5 =
2) ab + c > a + b + |c|.
If c > 0, (2) reduces to
3) ab > a + b
If c < 0, (2) reduces to
4) ab > a + b + 2|c|
5) |a - b + c|
To minimize (5), when c > 0, you want a < b, and when c < 0, you want a > b. And of course, you ideally want (5) to equal 0, and that's easy enough to set up. You can get (5) = 0 for a = b, a > 2, c = 0, n = a2 + 5. Work from there maybe. I don't know how to solve your problem, just thought I'd mention some things. If you continue in this manner, you may find your algorithm. Otherwise, I dunno- did you look at some prime factorizations? [shrug] Good luck.
Edit: Actually, why not just ditch the constant (n is any number in your sequence, so you can just add 5 back in later). Set c > 0 and a < b. Then I think your problem becomes finding solutions for:
6) n = ab + c
7) b - a = c
8) ab > a + b
(7) should make (5) = 0. You can try the other way (c < 0) if this doesn't work out. So some things are apparent now- like that c can't equal 0 unless n is a perfect square. Edit: If you play around with (6) and (7), you may discover a familiar form.

Last edited:

The problem of finding triplets for n in Brainf*** is an interesting and challenging one. The given conditions make it clear that we are looking for a, b, and c that can be used to efficiently represent n in the given programming language.

One possible approach to solving this problem is by using a brute force algorithm. We can start by trying different combinations of a, b, and c that satisfy the given conditions. For each combination, we can calculate the code length and compare it to the previous minimum code length. This process can continue until we find the combination that results in the minimum code length.

However, this approach may not be the most efficient one. The problem can also be approached using a dynamic programming approach. We can create a table that stores the minimum code length for each n value. Then, we can use this table to find the minimum code length for a given n by looking up the pre-calculated values. This approach would be more efficient as it avoids repeating the same calculations for different n values.

In terms of complexity analysis, the brute force approach would have a time complexity of O(n^3) as we would have to try all possible combinations of a, b, and c. On the other hand, the dynamic programming approach would have a time complexity of O(n) as we would only have to calculate the values once and then use them for further calculations.

In conclusion, finding triplets for n in Brainf*** is a fascinating problem that can be solved using different approaches. While the brute force approach may work for smaller values of n, the dynamic programming approach would be more efficient for larger values. It would also be interesting to explore other techniques such as recursion or backtracking to solve this problem.

## 1. What is Brainf***?

Brainf*** is a minimalistic programming language known for its simplicity and minimal syntax. It consists of only 8 commands and uses a tape of memory cells to store and manipulate data.

## 2. What is the purpose of finding triplets for n in Brainf***?

The purpose of finding triplets for n in Brainf*** is to optimize the algorithm for generating prime numbers in the language. This can improve the efficiency and speed of programs written in Brainf*** that involve prime numbers.

## 3. How does the algorithm for finding triplets for n in Brainf*** work?

The algorithm works by generating a sequence of numbers in the range of 2 to n and checking each number for its factors. If a number has exactly 3 factors, it is considered a triplet. This process is repeated until all numbers in the range have been checked.

## 4. What is the time complexity of the algorithm for finding triplets for n in Brainf***?

The time complexity of the algorithm is O(n^2) because it involves checking each number in the range of 2 to n and then checking its factors, which can also be up to n numbers.

## 5. Can this algorithm be used for other purposes besides finding triplets for n in Brainf***?

Yes, this algorithm can be used for finding prime numbers in general, not just in Brainf***. It can also be modified to find other types of numbers with a certain number of factors, such as quadruplets or quintuplets.

Replies
5
Views
1K
Replies
16
Views
2K
Replies
3
Views
1K
Replies
9
Views
2K
Replies
7
Views
2K
Replies
6
Views
2K
Replies
13
Views
2K
Replies
1
Views
2K
Replies
1
Views
1K
Replies
11
Views
1K