I am trying to construct a matrix with dimensions such that the number of unique off-diagonal elements (i.e. the number of elements in the upper or lower triangle) is proportional to a power of 2. By simplifying the expression somewhat, this essentially boils down to solving for all positive integer solutions to:
$$n^2 - n = c2^{J+1}\tag{1}$$
If I decide to include the diagonal elements of the matrix, the equation is then:
$$n^2 + n = c2^{J+1}\tag{2}$$
In both cases, $n$, $c$ and $J$ are integers.
Solve for equation (1), I get:
$$n = \frac{1 + \sqrt{1+c2^{J+3}}}{2}$$
Solve for equation (2), I get:
$$n = \frac{-1 + \sqrt{1+c2^{J+3}}}{2}$$
I'm a statistician working in the field of bioinformatics. The number theory methods needed to solve for $n$ are beyond me. Can anyone help me with an approach to solve either/both of these expressions?
The two equations can be solved in the excact same way, therefore I'm only going to solve the first one.
It has already been said in the comments that among the factors $n$ and $n-1$ only one must be even and the other most be odd. In order for this to happen, the power $2^{J+1}$ must be entirely contained in one of the two factors. This constraint does not leave many cases for us to study. In fact there are 6 cases:
A) $n=1$, $\ $ B) $n-1=1$, $\ $ C) $n=c$, $\ $ D) $n-1=c$, $\ $ E) $n|c$, $\ $ F) $(n-1)|c$
These are the only cases because, if n is odd, it can be either 1, c (with c odd) or a factor of c, since it cannot be the power of two or a factor of the power of 2. If n is even we get the other three cases.
I'm going to write the solutions in the form (n;c;J)
Let's take a look at the solutions for all the cases:
A) $n=1 \to c \cdot 2^{J+1}=0 \Rightarrow c=0 \ \forall J \in \Bbb N^+$
($2^{J+1}$ is never equal to $0$)
The solutions for this case are in the form $(1;0;J)$ for any positive integer J, and since $c$ is not positive, this solutions are not acceptable.
B) $n=2 \to c \cdot 2^{J+1}=2 \Rightarrow c \cdot 2^J=1 \Rightarrow c=1 \land J=0 \ \forall J \in \Bbb N^+$
(*The product of two positive integers is equal to $1$ only if both factors are equal to $1$)
The solution for this case is only one, and it is $(2;1;0)$, and since $J$ is not positive, this solution is not acceptable.
C) $n=c \to c^2-c=c\cdot 2^{J+1} \to c-1=2^{J+1} \to c=2^{J+1}+1 \ \forall J \in \Bbb N^+$
The solutions are in the form $(2^{J+1}+1; 2^{J+1}+1; J)$, and they are acceptable for any positive integer $J$
D) $n=c+1 \to c^2+c=c\cdot 2^{J+1} \to c+1=2^{J+1} \to c=2^{J+1}-1 \ \forall J \in \Bbb N^+$
The solutions are in the form $(2^{J+1}; 2^{J+1}-1; J)$, and they are acceptable for any positive integer $J$
E)$n|c \to c=nk \to n(n-1)=nk\cdot 2^{J+1} \to n-1=k2^{J+1} \to n=k2^{J+1}+1$
we can multiply both sides for k and get
$nk=c=k^22^{J+1}+k$
The solutions are in the form $(k2^{J+1}+1; k^22^{J+1}+k; J)$ and they are acceptable for any positive integers J and k.
F)$(n-1)|c \to c=(n-1)k \to n(n-1)=(n-1)k\cdot 2^{J+1} \to n=k2^{J+1}$
we can subtract 1 from both sides, multiply both sides by k and get
$(n-1)k=c=k^22^{J+1}-k$
The solutions are in the form $(k2^{J+1}; k^22^{J+1}-k; J)$ and they are acceptable for any positive integers J and k.
Note that the solutions C) and D) are respectively the solutions E) and F) in the case k=1 .
The solutions to this equation are:
$(k2^{J+1}+1; k^22^{J+1}+k; J)$
$(k2^{J+1}; k^22^{J+1}-k; J)$