0
$\begingroup$

Let $$f(n,k)=n\operatorname{mod} k, g(n,k)=\left\lfloor\frac{n}{k}\right\rfloor$$

Let $T(n,k)$ be A072030, i.e., array read by antidiagonals: $T(n,k)$ = number of steps in simple Euclidean algorithm for $\gcd(n,k)$ where $n\geqslant 1, k\geqslant 1$. Here $$T(n,k)=\begin{cases} 0,&\text{if $n<1$ or $k<1$;}\\ 1,&\text{if $n=k$;}\\ T(k,n),&\text{if $n<k$;}\\ T(k,n-k)+1,&\text{otherwise.} \end{cases}$$ Let $$R(n,k)=\begin{cases} 0,&\text{if $n<2$ or $k\geqslant n$;}\\ 2^{g(n,k)-2},&\text{if $f(n,k)=0$;}\\ 2^{T(k-f(n,k), f(n, k)) + g(n, k) - 1} + R(k, f(n, k)),&\text{otherwise.} \end{cases}$$ I conjecture that set of values of $R(n,k)$ (when we read it as triangle by rows) where $\frac{n}{k}$ is irreducible fraction such that $n,k\in\mathbb{N}$, $n>k\geqslant 1$ form a permutation of natural numbers.

Here is the PARI prog to verify this conjecture:

T(n, k) = if( n<1 || k<1, 0, if( n==k, 1, if( n<k, T(k, n), 1 + T(k, n-k)))) \\ from A072030 R(n, k)=if(n<2 || k>=n, 0, my(A=n%k, B=n\k); if(A==0, 2^(B-2), 2^(T(k-A, A) + B - 1) + R(k, A))) my(x=2, y=1); for(k=1, 299, while(!(R(x, y)==k), y++; if(x==y, x++; y=1, if(gcd(x,y)>1, y++; if(x==y, x++; y=1)))); print([x,y]); x=2; y=1);

It appears that irreducible fractions corresponding to each natural number are A071585/A071766.

Is there a way to prove it?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ This seems to be an over-complicated way of saying $$R(n,k) = \begin{cases} 0, & \text{if $k = 0$ or $k \geqslant n$;} \\ 2^{T(n, k) - 2} + R(k, n \bmod k),& \text{otherwise.}\end{cases}$$But if you define $$S(n,k) = \begin{cases} \emptyset, & \text{if $k = 0$ or $k \geqslant n$;} \\ \{T(n, k) - 2\} \cup S(k, n \bmod k),& \text{otherwise}\end{cases}$$ then I think you can strengthen the conjecture to say that the restriction of $S$ to $1 \leq k \leq n \wedge \gcd(n, k) = 1$ is bijective into $2^\mathbb{N}$. $\endgroup$ Commented Mar 1, 2023 at 12:10
  • 1
    $\begingroup$ And that combined with the example in A071585 gives the outline of how to prove that $S(n, k)$ is a slightly modified set of partial sums of the continued fraction of $\frac nk$. $\endgroup$ Commented Mar 2, 2023 at 8:27

0

Reset to default

You must log in to answer this question.