3 MathJax
source | link

GolfScript (23 chars)

{:^((1${\.**2^?%}+*}:f;

The sentinel result for a non-existent inverse is 0.

This is a simple application of Euler's theorem. x^{\varphi(2^n)} \equiv 1 \pmod {2^n}\$x^{\varphi(2^n)} \equiv 1 \pmod {2^n}\$, so x^{-1} \equiv x^{2^{n-1}-1} \pmod {2^n}\$x^{-1} \equiv x^{2^{n-1}-1} \pmod {2^n}\$

Unfortunately that's rather too big an exponential to compute directly, so we have to use a loop and do modular reduction inside the loop. The iterative step is x^{2^k-1} = \left(x^{2^{k-1}-1}\right)^2 \times x\$x^{2^k-1} = \left(x^{2^{k-1}-1}\right)^2 \times x\$ and we have a choice of base case: either k=1 with

{1\:^(@{\.**2^?%}+*}:f;

or k=2 with

{:^((1${\.**2^?%}+*}:f;

I'm working on another approach, but the sentinel is more difficult.

The key observation is that we can build the inverse up bit by bit: if xy \equiv 1 \pmod{2^{k-1}}\$xy \equiv 1 \pmod{2^{k-1}}\$ then xy \in { 1, 1 + 2^{k-1} } \pmod{2^k}\$xy \in \{ 1, 1 + 2^{k-1} \} \pmod{2^k}\$, and if x\$x\$ is odd we have x(y + xy-1) \equiv 1 \pmod{2^k}\$x(y + xy-1) \equiv 1 \pmod{2^k}\$. (If you're not convinced, check the two cases separately). So we can start at any suitable base case and apply the transformation y' = (x+1)y - 1\$y' = (x+1)y - 1\$ a suitable number of times.

Since 0x \equiv 1 \pmod {2^0}\$0x \equiv 1 \pmod {2^0}\$ we get, by induction

x\left(\frac{1 - (x+1)^n}{x}\right) \equiv 1 \pmod {2^n}\$x\left(\frac{1 - (x+1)^n}{x}\right) \equiv 1 \pmod {2^n}\$

where the inverse is the sum of a geometric sequence. I've shown the derivation to avoid the rabbit-out-of-a-hat effect: given this expression, it's easy to see that (given that the bracketed value is an integer, which follows from its derivation as a sum of an integer sequence) the product on the left must be in the right equivalence class if x+1\$x+1\$ is even.

That gives the 19-char function

{1$)1$?@/~)2@?%}:f;

which gives correct answers for inputs which have an inverse. However, it's not so simple when x\$x\$ is even. One potentially interesting option I've found is to add x&1 rather than 1.

{1$.1&+1$?@/~)2@?%}:f;

This seems to give sentinel values of either 0\$0\$ or 2^{n-1}\$2^{n-1}\$, but I haven't yet proved that.

Taking that one step further, we can ensure a sentinel of 0\$0\$ for even numbers by changing the expression 1 - (x+1)^n\$1 - (x+1)^n\$ into 1 - 1^n\$1 - 1^n\$:

{1$.1&*)1$?@/~)2@?%}:f;

That ties with the direct application of Euler's theorem for code length, but is going to have worse performance for large n\$n\$. If we take the arguments the other way round, as n x f, we can save one character and get to 22 chars:

{..1&*)2$?\/~)2@?%}:f;

GolfScript (23 chars)

{:^((1${\.**2^?%}+*}:f;

The sentinel result for a non-existent inverse is 0.

This is a simple application of Euler's theorem. x^{\varphi(2^n)} \equiv 1 \pmod {2^n}, so x^{-1} \equiv x^{2^{n-1}-1} \pmod {2^n}

Unfortunately that's rather too big an exponential to compute directly, so we have to use a loop and do modular reduction inside the loop. The iterative step is x^{2^k-1} = \left(x^{2^{k-1}-1}\right)^2 \times x and we have a choice of base case: either k=1 with

{1\:^(@{\.**2^?%}+*}:f;

or k=2 with

{:^((1${\.**2^?%}+*}:f;

I'm working on another approach, but the sentinel is more difficult.

The key observation is that we can build the inverse up bit by bit: if xy \equiv 1 \pmod{2^{k-1}} then xy \in { 1, 1 + 2^{k-1} } \pmod{2^k}, and if x is odd we have x(y + xy-1) \equiv 1 \pmod{2^k}. (If you're not convinced, check the two cases separately). So we can start at any suitable base case and apply the transformation y' = (x+1)y - 1 a suitable number of times.

Since 0x \equiv 1 \pmod {2^0} we get, by induction

x\left(\frac{1 - (x+1)^n}{x}\right) \equiv 1 \pmod {2^n}

where the inverse is the sum of a geometric sequence. I've shown the derivation to avoid the rabbit-out-of-a-hat effect: given this expression, it's easy to see that (given that the bracketed value is an integer, which follows from its derivation as a sum of an integer sequence) the product on the left must be in the right equivalence class if x+1 is even.

That gives the 19-char function

{1$)1$?@/~)2@?%}:f;

which gives correct answers for inputs which have an inverse. However, it's not so simple when x is even. One potentially interesting option I've found is to add x&1 rather than 1.

{1$.1&+1$?@/~)2@?%}:f;

This seems to give sentinel values of either 0 or 2^{n-1}, but I haven't yet proved that.

Taking that one step further, we can ensure a sentinel of 0 for even numbers by changing the expression 1 - (x+1)^n into 1 - 1^n:

{1$.1&*)1$?@/~)2@?%}:f;

That ties with the direct application of Euler's theorem for code length, but is going to have worse performance for large n. If we take the arguments the other way round, as n x f, we can save one character and get to 22 chars:

{..1&*)2$?\/~)2@?%}:f;

GolfScript (23 chars)

{:^((1${\.**2^?%}+*}:f;

The sentinel result for a non-existent inverse is 0.

This is a simple application of Euler's theorem. \$x^{\varphi(2^n)} \equiv 1 \pmod {2^n}\$, so \$x^{-1} \equiv x^{2^{n-1}-1} \pmod {2^n}\$

Unfortunately that's rather too big an exponential to compute directly, so we have to use a loop and do modular reduction inside the loop. The iterative step is \$x^{2^k-1} = \left(x^{2^{k-1}-1}\right)^2 \times x\$ and we have a choice of base case: either k=1 with

{1\:^(@{\.**2^?%}+*}:f;

or k=2 with

{:^((1${\.**2^?%}+*}:f;

I'm working on another approach, but the sentinel is more difficult.

The key observation is that we can build the inverse up bit by bit: if \$xy \equiv 1 \pmod{2^{k-1}}\$ then \$xy \in \{ 1, 1 + 2^{k-1} \} \pmod{2^k}\$, and if \$x\$ is odd we have \$x(y + xy-1) \equiv 1 \pmod{2^k}\$. (If you're not convinced, check the two cases separately). So we can start at any suitable base case and apply the transformation \$y' = (x+1)y - 1\$ a suitable number of times.

Since \$0x \equiv 1 \pmod {2^0}\$ we get, by induction

\$x\left(\frac{1 - (x+1)^n}{x}\right) \equiv 1 \pmod {2^n}\$

where the inverse is the sum of a geometric sequence. I've shown the derivation to avoid the rabbit-out-of-a-hat effect: given this expression, it's easy to see that (given that the bracketed value is an integer, which follows from its derivation as a sum of an integer sequence) the product on the left must be in the right equivalence class if \$x+1\$ is even.

That gives the 19-char function

{1$)1$?@/~)2@?%}:f;

which gives correct answers for inputs which have an inverse. However, it's not so simple when \$x\$ is even. One potentially interesting option I've found is to add x&1 rather than 1.

{1$.1&+1$?@/~)2@?%}:f;

This seems to give sentinel values of either \$0\$ or \$2^{n-1}\$, but I haven't yet proved that.

Taking that one step further, we can ensure a sentinel of \$0\$ for even numbers by changing the expression \$1 - (x+1)^n\$ into \$1 - 1^n\$:

{1$.1&*)1$?@/~)2@?%}:f;

That ties with the direct application of Euler's theorem for code length, but is going to have worse performance for large \$n\$. If we take the arguments the other way round, as n x f, we can save one character and get to 22 chars:

{..1&*)2$?\/~)2@?%}:f;
2 added 2098 characters in body
source | link

GolfScript (23 chars)

{:^((1${\.**2^?%}+*}:f;

The sentinel result for a non-existent inverse is 0.

This is a simple application of Euler's theorem. x^{\varphi(2^n)} \equiv 1 \pmod {2^n}, so x^{-1} \equiv x^{2^{n-1}-1} \pmod {2^n}

Unfortunately that's rather too big an exponential to compute directly, so we have to use a loop and do modular reduction inside the loop. The iterative step is x^{2^k-1} = \left(x^{2^{k-1}-1}\right)^2 \times x and we have a choice of base case: either k=1 with

{1\:^(@{\.**2^?%}+*}:f;

or k=2 with

{:^((1${\.**2^?%}+*}:f;

I'm working on another approach, but the sentinel is more difficult.

The key observation is that we can build the inverse up bit by bit: if xy \equiv 1 \pmod{2^{k-1}} then xy \in { 1, 1 + 2^{k-1} } \pmod{2^k}, and if x is odd we have x(y + xy-1) \equiv 1 \pmod{2^k}. (If you're not convinced, check the two cases separately). So we can start at any suitable base case and apply the transformation y' = (x+1)y - 1 a suitable number of times.

Since 0x \equiv 1 \pmod {2^0} we get, by induction

x\left(\frac{1 - (x+1)^n}{x}\right) \equiv 1 \pmod {2^n}

where the inverse is the sum of a geometric sequence. I've shown the derivation to avoid the rabbit-out-of-a-hat effect: given this expression, it's easy to see that (given that the bracketed value is an integer, which follows from its derivation as a sum of an integer sequence) the product on the left must be in the right equivalence class if x+1 is even.

That gives the 19-char function

{1$)1$?@/~)2@?%}:f;

which gives correct answers for inputs which have an inverse. However, it's not so simple when x is even. One potentially interesting option I've found is to add x&1 rather than 1.

{1$.1&+1$?@/~)2@?%}:f;

This seems to give sentinel values of either 0 or 2^{n-1}, but I haven't yet proved that.

Taking that one step further, we can ensure a sentinel of 0 for even numbers by changing the expression 1 - (x+1)^n into 1 - 1^n:

{1$.1&*)1$?@/~)2@?%}:f;

That ties with the direct application of Euler's theorem for code length, but is going to have worse performance for large n. If we take the arguments the other way round, as n x f, we can save one character and get to 22 chars:

{..1&*)2$?\/~)2@?%}:f;

GolfScript (23 chars)

{:^((1${\.**2^?%}+*}:f;

The sentinel result for a non-existent inverse is 0.

This is a simple application of Euler's theorem. x^{\varphi(2^n)} \equiv 1 \pmod {2^n}, so x^{-1} \equiv x^{2^{n-1}-1} \pmod {2^n}

Unfortunately that's rather too big an exponential to compute directly, so we have to use a loop and do modular reduction inside the loop. The iterative step is x^{2^k-1} = \left(x^{2^{k-1}-1}\right)^2 \times x and we have a choice of base case: either k=1 with

{1\:^(@{\.**2^?%}+*}:f;

or k=2 with

{:^((1${\.**2^?%}+*}:f;

GolfScript (23 chars)

{:^((1${\.**2^?%}+*}:f;

The sentinel result for a non-existent inverse is 0.

This is a simple application of Euler's theorem. x^{\varphi(2^n)} \equiv 1 \pmod {2^n}, so x^{-1} \equiv x^{2^{n-1}-1} \pmod {2^n}

Unfortunately that's rather too big an exponential to compute directly, so we have to use a loop and do modular reduction inside the loop. The iterative step is x^{2^k-1} = \left(x^{2^{k-1}-1}\right)^2 \times x and we have a choice of base case: either k=1 with

{1\:^(@{\.**2^?%}+*}:f;

or k=2 with

{:^((1${\.**2^?%}+*}:f;

I'm working on another approach, but the sentinel is more difficult.

The key observation is that we can build the inverse up bit by bit: if xy \equiv 1 \pmod{2^{k-1}} then xy \in { 1, 1 + 2^{k-1} } \pmod{2^k}, and if x is odd we have x(y + xy-1) \equiv 1 \pmod{2^k}. (If you're not convinced, check the two cases separately). So we can start at any suitable base case and apply the transformation y' = (x+1)y - 1 a suitable number of times.

Since 0x \equiv 1 \pmod {2^0} we get, by induction

x\left(\frac{1 - (x+1)^n}{x}\right) \equiv 1 \pmod {2^n}

where the inverse is the sum of a geometric sequence. I've shown the derivation to avoid the rabbit-out-of-a-hat effect: given this expression, it's easy to see that (given that the bracketed value is an integer, which follows from its derivation as a sum of an integer sequence) the product on the left must be in the right equivalence class if x+1 is even.

That gives the 19-char function

{1$)1$?@/~)2@?%}:f;

which gives correct answers for inputs which have an inverse. However, it's not so simple when x is even. One potentially interesting option I've found is to add x&1 rather than 1.

{1$.1&+1$?@/~)2@?%}:f;

This seems to give sentinel values of either 0 or 2^{n-1}, but I haven't yet proved that.

Taking that one step further, we can ensure a sentinel of 0 for even numbers by changing the expression 1 - (x+1)^n into 1 - 1^n:

{1$.1&*)1$?@/~)2@?%}:f;

That ties with the direct application of Euler's theorem for code length, but is going to have worse performance for large n. If we take the arguments the other way round, as n x f, we can save one character and get to 22 chars:

{..1&*)2$?\/~)2@?%}:f;
1
source | link

GolfScript (23 chars)

{:^((1${\.**2^?%}+*}:f;

The sentinel result for a non-existent inverse is 0.

This is a simple application of Euler's theorem. x^{\varphi(2^n)} \equiv 1 \pmod {2^n}, so x^{-1} \equiv x^{2^{n-1}-1} \pmod {2^n}

Unfortunately that's rather too big an exponential to compute directly, so we have to use a loop and do modular reduction inside the loop. The iterative step is x^{2^k-1} = \left(x^{2^{k-1}-1}\right)^2 \times x and we have a choice of base case: either k=1 with

{1\:^(@{\.**2^?%}+*}:f;

or k=2 with

{:^((1${\.**2^?%}+*}:f;