Code Golf

#13: Post edited by

trichoplax‭ · 2024-02-05T09:06:24Z (3 months ago)
Reinstate the changes from the previous 2 edits that my edit accidentally removed

Copy Link

Raw

Markdown

Print the modular multiplicative inverse / virtual fractions

~~### Goal~~
Print the [modular multiplicative inverse](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse) with a modulus of 65536 (or a higher exponent of 2) for odd numbers 1-97.
~~### Example output~~
Print these values (or an extension of them):
```
1
43691
52429
28087
36409
35747
20165
61167
61681
51739
53053
14247
23593
55827
49717
31711
33761
44939
7085
28567
39961
48771
20389
18127
22737
64251
21021
46471
60937
55539
38677
61375
4033
19563
4749
43383
61945
51555
14469
5807
18609
17371
64765
60263
18409
12243
54261
23455
41889
```
~~### Rules~~
- Use a modulus of at least $65536 = 2^{16}$. But you can use any modulus $ M = 2^N$ for $N ≥ 16$ and $N \in \mathbb{N} $ .
- Print the modular multiplicative inverse for at least all the natural, odd values $<98$.
- You can print it in any normal base.
- You can print additional stuff, but it should be clear which parts belong to the modular multiplicative inverse and which do not.
- Your program should print the required output in less than 1 hour on a modern PC (or other hardware that is affordable).
~~### Ungolfed example~~
```
#!/usr/bin/env python3
# Calculates the modular multiplicative inverse
def imod(a, n):
c=1
while c % a:
c+=n
return c//a
# Print the multiplicative inverse for 16-bit integers
n=2**16
for i in range(1,98,2): #For the values 1/1, 1/3, ... 1/97
b = imod(i,n)
print("{:>2} * 0x{:>04X} = {:2>} mod 0x{:>04X}".format(i,b,i*b%n,n))
```
-------
~~### Why these numbers are interesting~~
You don't have to understand this part in order to participate in the challenge.
There are multiple ways to look at these numbers. All lead to the same numbers. I call them **virtual fractions** (made up term). Virtual fractions are integers that have the feature that you can multiply them with the denominator and you get the numerator when you store them in a N-Bit integer. This only works for odd denominators. You can even add and multiply virtual fractions and they behave like you would expect from real fractions (assuming you use enough bits).
For example, you have the 16 bit unsigned integer with the value `0xAAAB` (43691). You can multiply it with 3 and get 1.
```
3 * 0xAAAB = 3 * 0b1010 1010 1010 1011 = 3 * 43691
= 0x20001 = 0b10 0000 0000 0000 0001 = 131073
Storing it in a 16 bit variable drops the 1 at bit 17:
= 0x0001 = 0b0000 0000 0000 0001 = 1
```
This does the following operation: $1 ≡ 3 \cdot 43691 \mod 65536$ (which would be `1%65536 == 43691%65536` or `1&0xFFFF == 43691&0xFFFF` in C). This is interesting because that is what a 16-Bit [ALU](https://en.wikipedia.org/wiki/Arithmetic_logic_unit) would do when it multiples `0xAAABu * 3u`.
Therefore, `0xAAAB` is like $1/3$.
There are other ways to look at these numbers, but that should be enough for this challenge.

## Goal
Print the [modular multiplicative inverse](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse) with a modulus of 65536 (or a higher exponent of 2) for odd numbers 1-97.
## Example output
Print these values (or an extension of them):
```
1
43691
52429
28087
36409
35747
20165
61167
61681
51739
53053
14247
23593
55827
49717
31711
33761
44939
7085
28567
39961
48771
20389
18127
22737
64251
21021
46471
60937
55539
38677
61375
4033
19563
4749
43383
61945
51555
14469
5807
18609
17371
64765
60263
18409
12243
54261
23455
41889
```
## Rules
- Use a modulus of at least $65536 = 2^{16}$. But you can use any modulus $ M = 2^N$ for $N ≥ 16$ and $N \in \mathbb{N} $ .
- Print the modular multiplicative inverse for at least all the natural, odd values $<98$.
- You can print it in any normal base.
- You can print additional stuff, but it should be clear which parts belong to the modular multiplicative inverse and which do not.
- Your program should print the required output in less than 1 hour on a modern PC (or other hardware that is affordable).
## Ungolfed example
```
#!/usr/bin/env python3
# Calculates the modular multiplicative inverse
def imod(a, n):
c=1
while c % a:
c+=n
return c//a
# Print the multiplicative inverse for 16-bit integers
n=2**16
for i in range(1,98,2): #For the values 1/1, 1/3, ... 1/97
b = imod(i,n)
print("{:>2} * 0x{:>04X} = {:2>} mod 0x{:>04X}".format(i,b,i*b%n,n))
```
-------
## Why these numbers are interesting
You don't have to understand this part in order to participate in the challenge.
There are multiple ways to look at these numbers. All lead to the same numbers. I call them **virtual fractions** (made up term). Virtual fractions are integers that have the feature that you can multiply them with the denominator and you get the numerator when you store them in a N-Bit integer. This only works for odd denominators. You can even add and multiply virtual fractions and they behave like you would expect from real fractions (assuming you use enough bits).
### Example for 1/3
For example, you have the 16 bit unsigned integer with the value `0xAAAB` (43691). You can multiply it with 3 and get 1.
```
3 * 0xAAAB = 3 * 0b1010 1010 1010 1011 = 3 * 43691
= 0x20001 = 0b10 0000 0000 0000 0001 = 131073
Storing it in a 16 bit variable drops the 1 at bit 17:
= 0x0001 = 0b0000 0000 0000 0001 = 1
```
This does the following operation: $1 ≡ 3 \cdot 43691 \mod 65536$ (which would be `1%65536 == 43691%65536` or `1&0xFFFF == 43691&0xFFFF` in C). This is interesting because that is what a 16-Bit [ALU](https://en.wikipedia.org/wiki/Arithmetic_logic_unit) would do when it multiples `0xAAABu * 3u`.
Therefore, `0xAAAB` is like $1/3$.
There are other ways to look at these numbers, but that should be enough for this challenge.

#12: Post edited by

trichoplax‭ · 2024-02-02T18:32:59Z (3 months ago)
Reduce ambiguity and typos, and add links

Copy Link

Raw

Markdown

Print the modular multiplicative inverse / virtual fractions

~~## Goal~~
~~Print the modular multiplicative inverse with a modulus of 65536 (or a higher exponent of 2) for odd numbers 1-97.~~
~~## Example output~~
~~Print this values (or an extension of them):~~
```
1
43691
52429
28087
36409
35747
20165
61167
61681
51739
53053
14247
23593
55827
49717
31711
33761
44939
7085
28567
39961
48771
20389
18127
22737
64251
21021
46471
60937
55539
38677
61375
4033
19563
4749
43383
61945
51555
14469
5807
18609
17371
64765
60263
18409
12243
54261
23455
41889
```
~~## Rules~~
~~- Use at least a modulus of $65536 = 2^{16}$. But you can use any $ M = 2^N$ for $N ≥ 16$ and $N \in \mathbb{N} $ .~~
~~- Print at least the modular multiplicative inverse of for the all natural, odd values $<98$.~~
~~- You can print it in any normal base~~
~~- You can print additional stuff, but it should be clear what parts belong to the modular multiplicative inverse and what not.~~
- Your program should print the required output in less than 1 hour on a modern PC (or other hardware that is affordable).
~~## Ungolfed example~~
```
#!/usr/bin/env python3
~~#Calculates the modular multiplicative inverse~~
def imod(a, n):
c=1
while c % a:
c+=n
return c//a
~~#Print the multiplicative inverse for 16-bit integers~~
n=2**16
for i in range(1,98,2): #For the values 1/1, 1/3, ... 1/97
b = imod(i,n)
print("{:>2} * 0x{:>04X} = {:2>} mod 0x{:>04X}".format(i,b,i*b%n,n))
```
-------
~~## Why this numbers are interesting~~
You don't have to understand this part in order to participate in the challenge.
There are multiple ways to look at this numbers. All lead to the same numbers. They can be used as i call them **virtual fractions** (made up term). Virtual fractions are integers that have the feature that you can multiply them with the denominator and you get the numerator when you store them in a N-Bit integer. This only works for odd denominators. You can even add and multiply virtual fractions and they behave like you would expect from real fractions (assuming you use enough bits).
~~#### Example for $1/3$~~
For example, you have the 16 bit unsigned integer with the value `0xAAAB` (43691). You can multiply it with 3 and get 1.
```
3 * 0xAAAB = 3 * 0b1010 1010 1010 1011 = 3 * 43691
= 0x20001 = 0b10 0000 0000 0000 0001 = 131073
Storing it in a 16 bit variable drops the 1 at bit 17:
= 0x0001 = 0b0000 0000 0000 0001 = 1
```
This does the following operation: $1 ≡ 3 \cdot 43691 \mod 65536$ (which would be `1%65536 == 43691%65536` or `1&0xFFFF == 43691&0xFFFF` in C). This is interesting because that is what a 16-Bit ALU would do when it multiples `0xAAABu * 3u`.
Therefore, `0xAAAB` is like $1/3$.
~~There are other ways to look at this numbers, but that should be enough for this challenge.~~

### Goal
Print the [modular multiplicative inverse](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse) with a modulus of 65536 (or a higher exponent of 2) for odd numbers 1-97.
### Example output
Print these values (or an extension of them):
```
1
43691
52429
28087
36409
35747
20165
61167
61681
51739
53053
14247
23593
55827
49717
31711
33761
44939
7085
28567
39961
48771
20389
18127
22737
64251
21021
46471
60937
55539
38677
61375
4033
19563
4749
43383
61945
51555
14469
5807
18609
17371
64765
60263
18409
12243
54261
23455
41889
```
### Rules
- Use a modulus of at least $65536 = 2^{16}$. But you can use any modulus $ M = 2^N$ for $N ≥ 16$ and $N \in \mathbb{N} $ .
- Print the modular multiplicative inverse for at least all the natural, odd values $<98$.
- You can print it in any normal base.
- You can print additional stuff, but it should be clear which parts belong to the modular multiplicative inverse and which do not.
- Your program should print the required output in less than 1 hour on a modern PC (or other hardware that is affordable).
### Ungolfed example
```
#!/usr/bin/env python3
# Calculates the modular multiplicative inverse
def imod(a, n):
c=1
while c % a:
c+=n
return c//a
# Print the multiplicative inverse for 16-bit integers
n=2**16
for i in range(1,98,2): #For the values 1/1, 1/3, ... 1/97
b = imod(i,n)
print("{:>2} * 0x{:>04X} = {:2>} mod 0x{:>04X}".format(i,b,i*b%n,n))
```
-------
### Why these numbers are interesting
You don't have to understand this part in order to participate in the challenge.
There are multiple ways to look at these numbers. All lead to the same numbers. I call them **virtual fractions** (made up term). Virtual fractions are integers that have the feature that you can multiply them with the denominator and you get the numerator when you store them in a N-Bit integer. This only works for odd denominators. You can even add and multiply virtual fractions and they behave like you would expect from real fractions (assuming you use enough bits).
For example, you have the 16 bit unsigned integer with the value `0xAAAB` (43691). You can multiply it with 3 and get 1.
```
3 * 0xAAAB = 3 * 0b1010 1010 1010 1011 = 3 * 43691
= 0x20001 = 0b10 0000 0000 0000 0001 = 131073
Storing it in a 16 bit variable drops the 1 at bit 17:
= 0x0001 = 0b0000 0000 0000 0001 = 1
```
This does the following operation: $1 ≡ 3 \cdot 43691 \mod 65536$ (which would be `1%65536 == 43691%65536` or `1&0xFFFF == 43691&0xFFFF` in C). This is interesting because that is what a 16-Bit [ALU](https://en.wikipedia.org/wiki/Arithmetic_logic_unit) would do when it multiples `0xAAABu * 3u`.
Therefore, `0xAAAB` is like $1/3$.
There are other ways to look at these numbers, but that should be enough for this challenge.

#11: Post edited by

H_H‭ · 2024-02-02T16:57:53Z (3 months ago)

Copy Link

Raw

Markdown

## Goal
Print the modular multiplicative inverse with a modulus of 65536 (or a higher exponent of 2) for odd numbers 1-97.
## Example output
Print this values (or an extension of them):
```
1
43691
52429
28087
36409
35747
20165
61167
61681
51739
53053
14247
23593
55827
49717
31711
33761
44939
7085
28567
39961
48771
20389
18127
22737
64251
21021
46471
60937
55539
38677
61375
4033
19563
4749
43383
61945
51555
14469
5807
18609
17371
64765
60263
18409
12243
54261
23455
41889
```
## Rules
- Use at least a modulus of $65536 = 2^{16}$. But you can use any $ M = 2^N$ for $N ≥ 16$ and $N \in \mathbb{N} $ .
- Print at least the modular multiplicative inverse of for the all natural, odd values $<98$.
- You can print it in any normal base
- You can print additional stuff, but it should be clear what parts belong to the modular multiplicative inverse and what not.
- Your program should print the required output in less than 1 hour on a modern PC (or other hardware that is affordable).
## Ungolfed example
```
#!/usr/bin/env python3
#Calculates the modular multiplicative inverse
def imod(a, n):
c=1
while c % a:
c+=n
return c//a
#Print the multiplicative inverse for 16-bit integers
n=2**16
for i in range(1,98,2): #For the values 1/1, 1/3, ... 1/97
b = imod(i,n)
print("{:>2} * 0x{:>04X} = {:2>} mod 0x{:>04X}".format(i,b,i*b%n,n))
```
-------
~~## Why this numbers are interesting.~~
You don't have to understand this part in order to participate in the challenge.
There are multiple ways to look at this numbers. All lead to the same numbers. They can be used as i call them **virtual fractions** (made up term). Virtual fractions are integers that have the feature that you can multiply them with the denominator and you get the numerator when you store them in a N-Bit integer. This only works for odd denominators. You can even add and multiply virtual fractions and they behave like you would expect from real fractions (assuming you use enough bits).
#### Example for $1/3$
For example, you have the 16 bit unsigned integer with the value `0xAAAB` (43691). You can multiply it with 3 and get 1.
```
3 * 0xAAAB = 3 * 0b1010 1010 1010 1011 = 3 * 43691
= 0x20001 = 0b10 0000 0000 0000 0001 = 131073
Storing it in a 16 bit variable drops the 1 at bit 17:
= 0x0001 = 0b0000 0000 0000 0001 = 1
```
This does the following operation: $1 ≡ 3 \cdot 43691 \mod 65536$ (which would be `1%65536 == 43691%65536` or `1&0xFFFF == 43691&0xFFFF` in C). This is interesting because that is what a 16-Bit ALU would do when it multiples `0xAAABu * 3u`.
Therefore, `0xAAAB` is like $1/3$.
There are other ways to look at this numbers, but that should be enough for this challenge.

## Goal
Print the modular multiplicative inverse with a modulus of 65536 (or a higher exponent of 2) for odd numbers 1-97.
## Example output
Print this values (or an extension of them):
```
1
43691
52429
28087
36409
35747
20165
61167
61681
51739
53053
14247
23593
55827
49717
31711
33761
44939
7085
28567
39961
48771
20389
18127
22737
64251
21021
46471
60937
55539
38677
61375
4033
19563
4749
43383
61945
51555
14469
5807
18609
17371
64765
60263
18409
12243
54261
23455
41889
```
## Rules
- Use at least a modulus of $65536 = 2^{16}$. But you can use any $ M = 2^N$ for $N ≥ 16$ and $N \in \mathbb{N} $ .
- Print at least the modular multiplicative inverse of for the all natural, odd values $<98$.
- You can print it in any normal base
- You can print additional stuff, but it should be clear what parts belong to the modular multiplicative inverse and what not.
- Your program should print the required output in less than 1 hour on a modern PC (or other hardware that is affordable).
## Ungolfed example
```
#!/usr/bin/env python3
#Calculates the modular multiplicative inverse
def imod(a, n):
c=1
while c % a:
c+=n
return c//a
#Print the multiplicative inverse for 16-bit integers
n=2**16
for i in range(1,98,2): #For the values 1/1, 1/3, ... 1/97
b = imod(i,n)
print("{:>2} * 0x{:>04X} = {:2>} mod 0x{:>04X}".format(i,b,i*b%n,n))
```
-------
## Why this numbers are interesting
You don't have to understand this part in order to participate in the challenge.
There are multiple ways to look at this numbers. All lead to the same numbers. They can be used as i call them **virtual fractions** (made up term). Virtual fractions are integers that have the feature that you can multiply them with the denominator and you get the numerator when you store them in a N-Bit integer. This only works for odd denominators. You can even add and multiply virtual fractions and they behave like you would expect from real fractions (assuming you use enough bits).
#### Example for $1/3$
For example, you have the 16 bit unsigned integer with the value `0xAAAB` (43691). You can multiply it with 3 and get 1.
```
3 * 0xAAAB = 3 * 0b1010 1010 1010 1011 = 3 * 43691
= 0x20001 = 0b10 0000 0000 0000 0001 = 131073
Storing it in a 16 bit variable drops the 1 at bit 17:
= 0x0001 = 0b0000 0000 0000 0001 = 1
```
This does the following operation: $1 ≡ 3 \cdot 43691 \mod 65536$ (which would be `1%65536 == 43691%65536` or `1&0xFFFF == 43691&0xFFFF` in C). This is interesting because that is what a 16-Bit ALU would do when it multiples `0xAAABu * 3u`.
Therefore, `0xAAAB` is like $1/3$.
There are other ways to look at this numbers, but that should be enough for this challenge.

#10: Post edited by

H_H‭ · 2024-02-02T16:57:23Z (3 months ago)

Copy Link

Raw

Markdown

~~### Goal~~
Print the modular multiplicative inverse with a modulus of 65536 (or a higher exponent of 2) for odd numbers 1-97.
~~### Example output~~
Print this values (or an extension of them):
```
1
43691
52429
28087
36409
35747
20165
61167
61681
51739
53053
14247
23593
55827
49717
31711
33761
44939
7085
28567
39961
48771
20389
18127
22737
64251
21021
46471
60937
55539
38677
61375
4033
19563
4749
43383
61945
51555
14469
5807
18609
17371
64765
60263
18409
12243
54261
23455
41889
```
~~### Rules~~
- Use at least a modulus of $65536 = 2^{16}$. But you can use any $ M = 2^N$ for $N ≥ 16$ and $N \in \mathbb{N} $ .
- Print at least the modular multiplicative inverse of for the all natural, odd values $<98$.
- You can print it in any normal base
- You can print additional stuff, but it should be clear what parts belong to the modular multiplicative inverse and what not.
- Your program should print the required output in less than 1 hour on a modern PC (or other hardware that is affordable).
~~### Ungolfed example~~
```
#!/usr/bin/env python3
#Calculates the modular multiplicative inverse
def imod(a, n):
c=1
while c % a:
c+=n
return c//a
#Print the multiplicative inverse for 16-bit integers
n=2**16
for i in range(1,98,2): #For the values 1/1, 1/3, ... 1/97
b = imod(i,n)
print("{:>2} * 0x{:>04X} = {:2>} mod 0x{:>04X}".format(i,b,i*b%n,n))
```
-------
~~### Why this numbers are interesting.~~
You don't have to understand this part in order to participate in the challenge.
There are multiple ways to look at this numbers. All lead to the same numbers. They can be used as i call them **virtual fractions** (made up term). Virtual fractions are integers that have the feature that you can multiply them with the denominator and you get the numerator when you store them in a N-Bit integer. This only works for odd denominators. You can even add and multiply virtual fractions and they behave like you would expect from real fractions (assuming you use enough bits).
For example, you have the 16 bit unsigned integer with the value `0xAAAB` (43691). You can multiply it with 3 and get 1.
```
3 * 0xAAAB = 3 * 0b1010 1010 1010 1011 = 3 * 43691
= 0x20001 = 0b10 0000 0000 0000 0001 = 131073
Storing it in a 16 bit variable drops the 1 at bit 17:
= 0x0001 = 0b0000 0000 0000 0001 = 1
```
This does the following operation: $1 ≡ 3 \cdot 43691 \mod 65536$ (which would be `1%65536 == 43691%65536` or `1&0xFFFF == 43691&0xFFFF` in C). This is interesting because that is what a 16-Bit ALU would do when it multiples `0xAAABu * 3u`.
Therefore, `0xAAAB` is like $1/3$.
There are other ways to look at this numbers, but that should be enough for this challenge.

## Goal
Print the modular multiplicative inverse with a modulus of 65536 (or a higher exponent of 2) for odd numbers 1-97.
## Example output
Print this values (or an extension of them):
```
1
43691
52429
28087
36409
35747
20165
61167
61681
51739
53053
14247
23593
55827
49717
31711
33761
44939
7085
28567
39961
48771
20389
18127
22737
64251
21021
46471
60937
55539
38677
61375
4033
19563
4749
43383
61945
51555
14469
5807
18609
17371
64765
60263
18409
12243
54261
23455
41889
```
## Rules
- Use at least a modulus of $65536 = 2^{16}$. But you can use any $ M = 2^N$ for $N ≥ 16$ and $N \in \mathbb{N} $ .
- Print at least the modular multiplicative inverse of for the all natural, odd values $<98$.
- You can print it in any normal base
- You can print additional stuff, but it should be clear what parts belong to the modular multiplicative inverse and what not.
- Your program should print the required output in less than 1 hour on a modern PC (or other hardware that is affordable).
## Ungolfed example
```
#!/usr/bin/env python3
#Calculates the modular multiplicative inverse
def imod(a, n):
c=1
while c % a:
c+=n
return c//a
#Print the multiplicative inverse for 16-bit integers
n=2**16
for i in range(1,98,2): #For the values 1/1, 1/3, ... 1/97
b = imod(i,n)
print("{:>2} * 0x{:>04X} = {:2>} mod 0x{:>04X}".format(i,b,i*b%n,n))
```
-------
## Why this numbers are interesting.
You don't have to understand this part in order to participate in the challenge.
There are multiple ways to look at this numbers. All lead to the same numbers. They can be used as i call them **virtual fractions** (made up term). Virtual fractions are integers that have the feature that you can multiply them with the denominator and you get the numerator when you store them in a N-Bit integer. This only works for odd denominators. You can even add and multiply virtual fractions and they behave like you would expect from real fractions (assuming you use enough bits).
#### Example for $1/3$
For example, you have the 16 bit unsigned integer with the value `0xAAAB` (43691). You can multiply it with 3 and get 1.
```
3 * 0xAAAB = 3 * 0b1010 1010 1010 1011 = 3 * 43691
= 0x20001 = 0b10 0000 0000 0000 0001 = 131073
Storing it in a 16 bit variable drops the 1 at bit 17:
= 0x0001 = 0b0000 0000 0000 0001 = 1
```
This does the following operation: $1 ≡ 3 \cdot 43691 \mod 65536$ (which would be `1%65536 == 43691%65536` or `1&0xFFFF == 43691&0xFFFF` in C). This is interesting because that is what a 16-Bit ALU would do when it multiples `0xAAABu * 3u`.
Therefore, `0xAAAB` is like $1/3$.
There are other ways to look at this numbers, but that should be enough for this challenge.

#9: Post edited by

H_H‭ · 2024-02-02T16:51:57Z (3 months ago)

Copy Link

Raw

Markdown

~~Print the modular multiplicative inverse / virtual fractions / 2-adic fractions~~

Print the modular multiplicative inverse / virtual fractions

### Goal
Print the modular multiplicative inverse with a modulus of 65536 (or a higher exponent of 2) for odd numbers 1-97.
### Example output
Print this values (or an extension of them):
```
1
43691
52429
28087
36409
35747
20165
61167
61681
51739
53053
14247
23593
55827
49717
31711
33761
44939
7085
28567
39961
48771
20389
18127
22737
64251
21021
46471
60937
55539
38677
61375
4033
19563
4749
43383
61945
51555
14469
5807
18609
17371
64765
60263
18409
12243
54261
23455
41889
```
### Rules
- Use at least a modulus of $65536 = 2^{16}$. But you can use any $ M = 2^N$ for $N ≥ 16$ and $N \in \mathbb{N} $ .
- Print at least the modular multiplicative inverse of for the all natural, odd values $<98$.
- You can print it in any normal base
- You can print additional stuff, but it should be clear what parts belong to the modular multiplicative inverse and what not.
- Your program should print the required output in less than 1 hour on a modern PC (or other hardware that is affordable).
### Ungolfed example
```
#!/usr/bin/env python3
#Calculates the modular multiplicative inverse
def imod(a, n):
c=1
while c % a:
c+=n
return c//a
~~#Print the virtual fractions for 16-bit integers~~
n=2**16
for i in range(1,98,2): #For the values 1/1, 1/3, ... 1/97
b = imod(i,n)
print("{:>2} * 0x{:>04X} = {:2>} mod 0x{:>04X}".format(i,b,i*b%n,n))
```
-------
### Why this numbers are interesting.
You don't have to understand this part in order to participate in the challenge.
There are multiple ways to look at this numbers. All lead to the same numbers. They can be used as virtual fractions. Virtual fractions (made up this term) are integers that have the feature that you can multiply them with the denominator and you get the numerator when you store them in a N-Bit integer. This only works for odd denominators. You can even add and multiply virtual fractions and they behave like you would expect from real fractions (assuming you use enough bits).
For example, you have the 16 bit unsigned integer with the value `0xAAAB` (43691). You can multiply it with 3 and get 1.
```
3 * 0xAAAB = 3 * 0b1010 1010 1010 1011 = 3 * 43691
= 0x20001 = 0b10 0000 0000 0000 0001 = 131073
Storing it in a 16 bit variable drops the 1 at bit 17:
= 0x0001 = 0b0000 0000 0000 0001 = 1
```
This does the following operation: $1 ≡ 3 \cdot 43691 \mod 65536$ (which would be `1%65536 == 43691%65536` or `1&0xFFFF == 43691&0xFFFF` in C). This is interesting because that is what a 16-Bit ALU would do when it multiples `0xAAABu * 3u`.
Therefore, `0xAAAB` is like $1/3$.
There are other ways to look at this numbers, but that should be enough for this challenge.

### Goal
Print the modular multiplicative inverse with a modulus of 65536 (or a higher exponent of 2) for odd numbers 1-97.
### Example output
Print this values (or an extension of them):
```
1
43691
52429
28087
36409
35747
20165
61167
61681
51739
53053
14247
23593
55827
49717
31711
33761
44939
7085
28567
39961
48771
20389
18127
22737
64251
21021
46471
60937
55539
38677
61375
4033
19563
4749
43383
61945
51555
14469
5807
18609
17371
64765
60263
18409
12243
54261
23455
41889
```
### Rules
- Use at least a modulus of $65536 = 2^{16}$. But you can use any $ M = 2^N$ for $N ≥ 16$ and $N \in \mathbb{N} $ .
- Print at least the modular multiplicative inverse of for the all natural, odd values $<98$.
- You can print it in any normal base
- You can print additional stuff, but it should be clear what parts belong to the modular multiplicative inverse and what not.
- Your program should print the required output in less than 1 hour on a modern PC (or other hardware that is affordable).
### Ungolfed example
```
#!/usr/bin/env python3
#Calculates the modular multiplicative inverse
def imod(a, n):
c=1
while c % a:
c+=n
return c//a
#Print the multiplicative inverse for 16-bit integers
n=2**16
for i in range(1,98,2): #For the values 1/1, 1/3, ... 1/97
b = imod(i,n)
print("{:>2} * 0x{:>04X} = {:2>} mod 0x{:>04X}".format(i,b,i*b%n,n))
```
-------
### Why this numbers are interesting.
You don't have to understand this part in order to participate in the challenge.
There are multiple ways to look at this numbers. All lead to the same numbers. They can be used as i call them **virtual fractions** (made up term). Virtual fractions are integers that have the feature that you can multiply them with the denominator and you get the numerator when you store them in a N-Bit integer. This only works for odd denominators. You can even add and multiply virtual fractions and they behave like you would expect from real fractions (assuming you use enough bits).
For example, you have the 16 bit unsigned integer with the value `0xAAAB` (43691). You can multiply it with 3 and get 1.
```
3 * 0xAAAB = 3 * 0b1010 1010 1010 1011 = 3 * 43691
= 0x20001 = 0b10 0000 0000 0000 0001 = 131073
Storing it in a 16 bit variable drops the 1 at bit 17:
= 0x0001 = 0b0000 0000 0000 0001 = 1
```
This does the following operation: $1 ≡ 3 \cdot 43691 \mod 65536$ (which would be `1%65536 == 43691%65536` or `1&0xFFFF == 43691&0xFFFF` in C). This is interesting because that is what a 16-Bit ALU would do when it multiples `0xAAABu * 3u`.
Therefore, `0xAAAB` is like $1/3$.
There are other ways to look at this numbers, but that should be enough for this challenge.

#8: Post edited by

H_H‭ · 2024-02-02T16:45:02Z (3 months ago)

Copy Link

Raw

Markdown

### Goal
Print the modular multiplicative inverse with a modulus of 65536 (or a higher exponent of 2) for odd numbers 1-97.
### Example output
Print this values (or an extension of them):
```
1
43691
52429
28087
36409
35747
20165
61167
61681
51739
53053
14247
23593
55827
49717
31711
33761
44939
7085
28567
39961
48771
20389
18127
22737
64251
21021
46471
60937
55539
38677
61375
4033
19563
4749
43383
61945
51555
14469
5807
18609
17371
64765
60263
18409
12243
54261
23455
41889
```
### Rules
- Use at least a modulus of $65536 = 2^{16}$. But you can use any $ M = 2^N$ for $N ≥ 16$ and $N \in \mathbb{N} $ .
- Print at least the modular multiplicative inverse of for the all natural, odd values $<98$.
- You can print it in any normal base
- You can print additional stuff, but it should be clear what parts belong to the modular multiplicative inverse and what not.
~~- Your program should print the required output in less than 1 h on a modern PC (or other hardware that is affordable).~~
### Ungolfed example
```
#!/usr/bin/env python3
#Calculates the modular multiplicative inverse
def imod(a, n):
c=1
while c % a:
c+=n
return c//a
#Print the virtual fractions for 16-bit integers
n=2**16
for i in range(1,98,2): #For the values 1/1, 1/3, ... 1/97
b = imod(i,n)
print("{:>2} * 0x{:>04X} = {:2>} mod 0x{:>04X}".format(i,b,i*b%n,n))
```
-------
### Explanation
You don't have to understand this part in order to participate in the challenge.
There are multiple ways to look at this numbers. All lead to the same numbers. The 2. way is as virtual fractions. virtual fractions are integers that have the feature that you can multiply them with the denominator and you get the numerator when you store them in a N-Bit integer. This only works for odd denominators. You can even add and multiply virtual fractions and they behave like you would expect from real fractions (assuming you use enough bits).
For example, you have the 16 bit unsigned integer with the value `0xAAAB` (43691). You can multiply it with 3 and get 1.
```
3 * 0xAAAB = 3 * 0b1010 1010 1010 1011 = 3 * 43691
= 0x20001 = 0b10 0000 0000 0000 0001 = 131073
Storing it in a 16 bit variable drops the 1 at bit 17:
= 0x0001 = 0b0000 0000 0000 0001 = 1
```
This does the following operation: $1 ≡ 3 \cdot 43691 \mod 65536$ (which would be `1%65536 == 43691%65536` or `1&0xFFFF == 43691&0xFFFF` in C). This is interesting because that is what a 16-Bit ALU would do when it multiples `0xAAABu * 3u`.
Therefore, `0xAAAB` is like $1/3$.
There are other ways to look at this numbers, but that should be enough for this challenge.

### Goal
Print the modular multiplicative inverse with a modulus of 65536 (or a higher exponent of 2) for odd numbers 1-97.
### Example output
Print this values (or an extension of them):
```
1
43691
52429
28087
36409
35747
20165
61167
61681
51739
53053
14247
23593
55827
49717
31711
33761
44939
7085
28567
39961
48771
20389
18127
22737
64251
21021
46471
60937
55539
38677
61375
4033
19563
4749
43383
61945
51555
14469
5807
18609
17371
64765
60263
18409
12243
54261
23455
41889
```
### Rules
- Use at least a modulus of $65536 = 2^{16}$. But you can use any $ M = 2^N$ for $N ≥ 16$ and $N \in \mathbb{N} $ .
- Print at least the modular multiplicative inverse of for the all natural, odd values $<98$.
- You can print it in any normal base
- You can print additional stuff, but it should be clear what parts belong to the modular multiplicative inverse and what not.
- Your program should print the required output in less than 1 hour on a modern PC (or other hardware that is affordable).
### Ungolfed example
```
#!/usr/bin/env python3
#Calculates the modular multiplicative inverse
def imod(a, n):
c=1
while c % a:
c+=n
return c//a
#Print the virtual fractions for 16-bit integers
n=2**16
for i in range(1,98,2): #For the values 1/1, 1/3, ... 1/97
b = imod(i,n)
print("{:>2} * 0x{:>04X} = {:2>} mod 0x{:>04X}".format(i,b,i*b%n,n))
```
-------
### Why this numbers are interesting.
You don't have to understand this part in order to participate in the challenge.
There are multiple ways to look at this numbers. All lead to the same numbers. They can be used as virtual fractions. Virtual fractions (made up this term) are integers that have the feature that you can multiply them with the denominator and you get the numerator when you store them in a N-Bit integer. This only works for odd denominators. You can even add and multiply virtual fractions and they behave like you would expect from real fractions (assuming you use enough bits).
For example, you have the 16 bit unsigned integer with the value `0xAAAB` (43691). You can multiply it with 3 and get 1.
```
3 * 0xAAAB = 3 * 0b1010 1010 1010 1011 = 3 * 43691
= 0x20001 = 0b10 0000 0000 0000 0001 = 131073
Storing it in a 16 bit variable drops the 1 at bit 17:
= 0x0001 = 0b0000 0000 0000 0001 = 1
```
This does the following operation: $1 ≡ 3 \cdot 43691 \mod 65536$ (which would be `1%65536 == 43691%65536` or `1&0xFFFF == 43691&0xFFFF` in C). This is interesting because that is what a 16-Bit ALU would do when it multiples `0xAAABu * 3u`.
Therefore, `0xAAAB` is like $1/3$.
There are other ways to look at this numbers, but that should be enough for this challenge.

#7: Post edited by

H_H‭ · 2024-02-02T14:03:02Z (3 months ago)

Copy Link

Raw

Markdown

### Goal
Print the modular multiplicative inverse with a modulus of 65536 (or a higher exponent of 2) for odd numbers 1-97.
### Example output
Print this values (or an extension of them):
```
1
43691
52429
28087
36409
35747
20165
61167
61681
51739
53053
14247
23593
55827
49717
31711
33761
44939
7085
28567
39961
48771
20389
18127
22737
64251
21021
46471
60937
55539
38677
61375
4033
19563
4749
43383
61945
51555
14469
5807
18609
17371
64765
60263
18409
12243
54261
23455
41889
```
### Rules
- Use at least a modulus of $65536 = 2^{16}$. But you can use any $ M = 2^N$ for $N ≥ 16$ and $N \in \mathbb{N} $ .
- Print at least the modular multiplicative inverse of for the all natural, odd values $<98$.
- You can print it in any normal base
- You can print additional stuff, but it should be clear what parts belong to the modular multiplicative inverse and what not.
- Your program should print the required output in less than 1 h on a modern PC (or other hardware that is affordable).
### Ungolfed example
```
#!/usr/bin/env python3
#Calculates the modular multiplicative inverse
def imod(a, n):
c=1
while c % a:
c+=n
return c//a
#Print the virtual fractions for 16-bit integers
n=2**16
for i in range(1,98,2): #For the values 1/1, 1/3, ... 1/97
b = imod(i,n)
print("{:>2} * 0x{:>04X} = {:2>} mod 0x{:>04X}".format(i,b,i*b%n,n))
```
-------
### Explanation
You don't have to understand this part in order to participate in the challenge.
There are at least 3 ways to look at this numbers. All lead to the same numbers. The 2. way is as virtual fractions. virtual fractions are integers that have the feature that you can multiply them with the denominator and you get the numerator when you store them in a N-Bit integer.
For example, you have the 16 bit unsigned integer with the value `0xAAAB` (43691). You can multiply it with 3 and get 1.
```
3 * 0xAAAB = 3 * 0b1010 1010 1010 1011 = 3 * 43691
= 0x20001 = 0b10 0000 0000 0000 0001 = 131073
Storing it in a 16 bit variable drops the 1 at bit 17:
= 0x0001 = 0b0000 0000 0000 0001 = 1
```
This does the following operation: $1 ≡ 3 \cdot 43691 \mod 65536$ (which would be `1%65536 == 43691%65536` or `1&0xFFFF == 43691&0xFFFF` in C). This is interesting because that is what a 16-Bit ALU would do when it multiples `0xAAABu * 3u`.
A 3. way of looking at them is by looking as P-adic numbers. A P-adic number is number, written in base P, that has an infinite amount of digits to the left. And you can add and multiply this values and you get other 2-adic fractions like you would expect from normal fractions.
In this case it would be a 2-adic number since computer work in binary. And since we have limited amount of memory, we limited this challenge to 16 binary digits, which makes them non-P-adic anymore.

### Goal
Print the modular multiplicative inverse with a modulus of 65536 (or a higher exponent of 2) for odd numbers 1-97.
### Example output
Print this values (or an extension of them):
```
1
43691
52429
28087
36409
35747
20165
61167
61681
51739
53053
14247
23593
55827
49717
31711
33761
44939
7085
28567
39961
48771
20389
18127
22737
64251
21021
46471
60937
55539
38677
61375
4033
19563
4749
43383
61945
51555
14469
5807
18609
17371
64765
60263
18409
12243
54261
23455
41889
```
### Rules
- Use at least a modulus of $65536 = 2^{16}$. But you can use any $ M = 2^N$ for $N ≥ 16$ and $N \in \mathbb{N} $ .
- Print at least the modular multiplicative inverse of for the all natural, odd values $<98$.
- You can print it in any normal base
- You can print additional stuff, but it should be clear what parts belong to the modular multiplicative inverse and what not.
- Your program should print the required output in less than 1 h on a modern PC (or other hardware that is affordable).
### Ungolfed example
```
#!/usr/bin/env python3
#Calculates the modular multiplicative inverse
def imod(a, n):
c=1
while c % a:
c+=n
return c//a
#Print the virtual fractions for 16-bit integers
n=2**16
for i in range(1,98,2): #For the values 1/1, 1/3, ... 1/97
b = imod(i,n)
print("{:>2} * 0x{:>04X} = {:2>} mod 0x{:>04X}".format(i,b,i*b%n,n))
```
-------
### Explanation
You don't have to understand this part in order to participate in the challenge.
There are multiple ways to look at this numbers. All lead to the same numbers. The 2. way is as virtual fractions. virtual fractions are integers that have the feature that you can multiply them with the denominator and you get the numerator when you store them in a N-Bit integer. This only works for odd denominators. You can even add and multiply virtual fractions and they behave like you would expect from real fractions (assuming you use enough bits).
For example, you have the 16 bit unsigned integer with the value `0xAAAB` (43691). You can multiply it with 3 and get 1.
```
3 * 0xAAAB = 3 * 0b1010 1010 1010 1011 = 3 * 43691
= 0x20001 = 0b10 0000 0000 0000 0001 = 131073
Storing it in a 16 bit variable drops the 1 at bit 17:
= 0x0001 = 0b0000 0000 0000 0001 = 1
```
This does the following operation: $1 ≡ 3 \cdot 43691 \mod 65536$ (which would be `1%65536 == 43691%65536` or `1&0xFFFF == 43691&0xFFFF` in C). This is interesting because that is what a 16-Bit ALU would do when it multiples `0xAAABu * 3u`.
Therefore, `0xAAAB` is like $1/3$.
There are other ways to look at this numbers, but that should be enough for this challenge.

#6: Post edited by

H_H‭ · 2024-02-02T13:56:07Z (3 months ago)

Copy Link

Raw

Markdown

### Goal
Print the modular multiplicative inverse with a modulus of 65536 (or a higher exponent of 2) for odd numbers 1-97.
### Example output
Print this values (or an extension of them):
```
1
43691
52429
28087
36409
35747
20165
61167
61681
51739
53053
14247
23593
55827
49717
31711
33761
44939
7085
28567
39961
48771
20389
18127
22737
64251
21021
46471
60937
55539
38677
61375
4033
19563
4749
43383
61945
51555
14469
5807
18609
17371
64765
60263
18409
12243
54261
23455
41889
```
### Rules
- Use at least a modulus of $65536 = 2^{16}$. But you can use any $ M = 2^N$ for $N ≥ 16$ and $N \in \mathbb{N} $ .
- Print at least the modular multiplicative inverse of for the all natural, odd values $<98$.
- You can print it in any normal base
- You can print additional stuff, but it should be clear what parts belong to the modular multiplicative inverse and what not.
- Your program should print the required output in less than 1 h on a modern PC (or other hardware that is affordable).
### Ungolfed example
```
#!/usr/bin/env python3
#Calculates the modular multiplicative inverse
def imod(a, n):
c=1
while c % a:
c+=n
return c//a
#Print the virtual fractions for 16-bit integers
n=2**16
for i in range(1,98,2): #For the values 1/1, 1/3, ... 1/97
b = imod(i,n)
print("{:>2} * 0x{:>04X} = {:2>} mod 0x{:>04X}".format(i,b,i*b%n,n))
```
-------
### Explanation
You don't have to understand this part in order to participate in the challenge.
There are at least 3 ways to look at this numbers. All lead to the same numbers. The 2. way is as virtual fractions. virtual fractions are integers that have the feature that you can multiply them with the denominator and you get the numerator when you store them in a N-Bit integer.
For example, you have the 16 bit unsigned integer with the value `0xAAAB` (43691). You can multiply it with 3 and get 1.
```
3 * 0xAAAB = 3 * 0b1010 1010 1010 1011 = 3 * 43691
= 0x20001 = 0b10 0000 0000 0000 0001 = 131073
Storing it in a 16 bit variable drops the 1 at bit 17:
= 0x0001 = 0b0000 0000 0000 0001 = 1
```
This does the following operation: $1 ≡ 3 \cdot 43691 \mod 65536$ (which would be `1%65536 == 43691%65536` or `1&0xFFFF == 43691&0xFFFF` in C). This is interesting because that is what a 16-Bit ALU would do when it multiples `0xAAABu * 3u`.
A 3. way of looking at them is by looking as P-adic numbers. A P-adic number is number, written in base P, that has an infinite amount of digits to the left. And you can add and multiply this values and you get other virtual fractions like you would expect from normal fractions.
In this case it would be a 2-adic number since computer work in binary. And since we have limited amount of memory, we limited this challenge to 16 binary digits, which makes them non-P-adic anymore.

### Goal
Print the modular multiplicative inverse with a modulus of 65536 (or a higher exponent of 2) for odd numbers 1-97.
### Example output
Print this values (or an extension of them):
```
1
43691
52429
28087
36409
35747
20165
61167
61681
51739
53053
14247
23593
55827
49717
31711
33761
44939
7085
28567
39961
48771
20389
18127
22737
64251
21021
46471
60937
55539
38677
61375
4033
19563
4749
43383
61945
51555
14469
5807
18609
17371
64765
60263
18409
12243
54261
23455
41889
```
### Rules
- Use at least a modulus of $65536 = 2^{16}$. But you can use any $ M = 2^N$ for $N ≥ 16$ and $N \in \mathbb{N} $ .
- Print at least the modular multiplicative inverse of for the all natural, odd values $<98$.
- You can print it in any normal base
- You can print additional stuff, but it should be clear what parts belong to the modular multiplicative inverse and what not.
- Your program should print the required output in less than 1 h on a modern PC (or other hardware that is affordable).
### Ungolfed example
```
#!/usr/bin/env python3
#Calculates the modular multiplicative inverse
def imod(a, n):
c=1
while c % a:
c+=n
return c//a
#Print the virtual fractions for 16-bit integers
n=2**16
for i in range(1,98,2): #For the values 1/1, 1/3, ... 1/97
b = imod(i,n)
print("{:>2} * 0x{:>04X} = {:2>} mod 0x{:>04X}".format(i,b,i*b%n,n))
```
-------
### Explanation
You don't have to understand this part in order to participate in the challenge.
There are at least 3 ways to look at this numbers. All lead to the same numbers. The 2. way is as virtual fractions. virtual fractions are integers that have the feature that you can multiply them with the denominator and you get the numerator when you store them in a N-Bit integer.
For example, you have the 16 bit unsigned integer with the value `0xAAAB` (43691). You can multiply it with 3 and get 1.
```
3 * 0xAAAB = 3 * 0b1010 1010 1010 1011 = 3 * 43691
= 0x20001 = 0b10 0000 0000 0000 0001 = 131073
Storing it in a 16 bit variable drops the 1 at bit 17:
= 0x0001 = 0b0000 0000 0000 0001 = 1
```
This does the following operation: $1 ≡ 3 \cdot 43691 \mod 65536$ (which would be `1%65536 == 43691%65536` or `1&0xFFFF == 43691&0xFFFF` in C). This is interesting because that is what a 16-Bit ALU would do when it multiples `0xAAABu * 3u`.
A 3. way of looking at them is by looking as P-adic numbers. A P-adic number is number, written in base P, that has an infinite amount of digits to the left. And you can add and multiply this values and you get other 2-adic fractions like you would expect from normal fractions.
In this case it would be a 2-adic number since computer work in binary. And since we have limited amount of memory, we limited this challenge to 16 binary digits, which makes them non-P-adic anymore.

#5: Post edited by

H_H‭ · 2024-02-02T11:36:54Z (3 months ago)

Copy Link

Raw

Markdown

### Goal
Print the modular multiplicative inverse with a modulus of 65536 (or a higher exponent of 2) for odd numbers 1-97.
### Example output
Print this values (or an extension of them):
```
1
43691
52429
28087
36409
35747
20165
61167
61681
51739
53053
14247
23593
55827
49717
31711
33761
44939
7085
28567
39961
48771
20389
18127
22737
64251
21021
46471
60937
55539
38677
61375
4033
19563
4749
43383
61945
51555
14469
5807
18609
17371
64765
60263
18409
12243
54261
23455
41889
```
### Rules
- Use at least a modulus of $65536 = 2^{16}$. But you can use any $ M = 2^N$ for $N ≥ 16$ and $N \in \mathbb{N} $ .
- Print at least the modular multiplicative inverse of for the all natural, odd values $<98$.
- You can print it in any normal base
- You can print additional stuff, but it should be clear what parts belong to the modular multiplicative inverse and what not.
- Your program should print the required output in less than 1 h on a modern PC (or other hardware that is affordable).
### Ungolfed example
```
#!/usr/bin/env python3
#Calculates the modular multiplicative inverse
def imod(a, n):
c=1
while c % a:
c+=n
return c//a
#Print the virtual fractions for 16-bit integers
n=2**16
for i in range(1,98,2): #For the values 1/1, 1/3, ... 1/97
b = imod(i,n)
print("{:>2} * 0x{:>04X} = {:2>} mod 0x{:>04X}".format(i,b,i*b%n,n))
```
-------
### Explanation
~~You don't have to understand the part in order to participate in the challenge.~~
There are at least 3 ways to look at this numbers. All lead to the same results. The 2. way is as virtual fractions. virtual fractions are integers that have the feature that you can multiply them with the denominator and you get the numerator when you store them in a N-Bit integer.
For example, you have the 16 bit unsigned integer with the value `0xAAAB` (43691). You can multiply it with 3 and get 1.
```
3 * 0xAAAB = 3 * 0b1010 1010 1010 1011 = 3 * 43691
= 0x20001 = 0b10 0000 0000 0000 0001 = 131073
Storing it in a 16 bit variable drops the 1 at bit 17:
= 0x0001 = 0b0000 0000 0000 0001 = 1
```
This does the following operation: $1 ≡ 3 \cdot 43691 \mod 65536$ (which would be `1%65536 == 43691%65536` or `1&0xFFFF == 43691&0xFFFF` in C). This is interesting because that is what a 16-Bit ALU would do when it multiples `0xAAABu * 3u`.
A 3. way of looking at them is by looking as P-adic numbers. A P-adic number is number, written in base P, that has an infinite amount of digits to the left. And you can add and multiply this values and you get other virtual fractions like you would expect from normal fractions.
In this case it would be a 2-adic number since computer work in binary. And since we have limited amount of memory, we limited this challenge to 16 binary digits, which makes them non-P-adic anymore.

### Goal
Print the modular multiplicative inverse with a modulus of 65536 (or a higher exponent of 2) for odd numbers 1-97.
### Example output
Print this values (or an extension of them):
```
1
43691
52429
28087
36409
35747
20165
61167
61681
51739
53053
14247
23593
55827
49717
31711
33761
44939
7085
28567
39961
48771
20389
18127
22737
64251
21021
46471
60937
55539
38677
61375
4033
19563
4749
43383
61945
51555
14469
5807
18609
17371
64765
60263
18409
12243
54261
23455
41889
```
### Rules
- Use at least a modulus of $65536 = 2^{16}$. But you can use any $ M = 2^N$ for $N ≥ 16$ and $N \in \mathbb{N} $ .
- Print at least the modular multiplicative inverse of for the all natural, odd values $<98$.
- You can print it in any normal base
- You can print additional stuff, but it should be clear what parts belong to the modular multiplicative inverse and what not.
- Your program should print the required output in less than 1 h on a modern PC (or other hardware that is affordable).
### Ungolfed example
```
#!/usr/bin/env python3
#Calculates the modular multiplicative inverse
def imod(a, n):
c=1
while c % a:
c+=n
return c//a
#Print the virtual fractions for 16-bit integers
n=2**16
for i in range(1,98,2): #For the values 1/1, 1/3, ... 1/97
b = imod(i,n)
print("{:>2} * 0x{:>04X} = {:2>} mod 0x{:>04X}".format(i,b,i*b%n,n))
```
-------
### Explanation
You don't have to understand this part in order to participate in the challenge.
There are at least 3 ways to look at this numbers. All lead to the same numbers. The 2. way is as virtual fractions. virtual fractions are integers that have the feature that you can multiply them with the denominator and you get the numerator when you store them in a N-Bit integer.
For example, you have the 16 bit unsigned integer with the value `0xAAAB` (43691). You can multiply it with 3 and get 1.
```
3 * 0xAAAB = 3 * 0b1010 1010 1010 1011 = 3 * 43691
= 0x20001 = 0b10 0000 0000 0000 0001 = 131073
Storing it in a 16 bit variable drops the 1 at bit 17:
= 0x0001 = 0b0000 0000 0000 0001 = 1
```
This does the following operation: $1 ≡ 3 \cdot 43691 \mod 65536$ (which would be `1%65536 == 43691%65536` or `1&0xFFFF == 43691&0xFFFF` in C). This is interesting because that is what a 16-Bit ALU would do when it multiples `0xAAABu * 3u`.
A 3. way of looking at them is by looking as P-adic numbers. A P-adic number is number, written in base P, that has an infinite amount of digits to the left. And you can add and multiply this values and you get other virtual fractions like you would expect from normal fractions.
In this case it would be a 2-adic number since computer work in binary. And since we have limited amount of memory, we limited this challenge to 16 binary digits, which makes them non-P-adic anymore.

#4: Post edited by

H_H‭ · 2024-02-02T11:32:45Z (3 months ago)

Copy Link

Raw

Markdown

~~Print virtual fractions / 2-adic fractions / Modular multiplicative inverse~~

Print the modular multiplicative inverse / virtual fractions / 2-adic fractions

### TL;DR
Print this values (or an extension of them):
```
1
43691
52429
28087
36409
35747
20165
61167
61681
51739
53053
14247
23593
55827
49717
31711
33761
44939
7085
28567
39961
48771
20389
18127
22737
64251
21021
46471
60937
55539
38677
61375
4033
19563
4749
43383
61945
51555
14469
5807
18609
17371
64765
60263
18409
12243
54261
23455
41889
```
-------
~~### Explanation~~
~~Virtual fractions are integers that have the feature that you can multiply them with the denominator and you get the numerator when you store them in a N-Bit integer.~~
~~For example, you have the 16 bit unsigned integer with the value `0xAAAB` (43691). You can multiply it with 3 and get 1.~~
~~```~~
~~3 * 0xAAAB = 3 * 0b1010 1010 1010 1011 = 3 * 43691~~
~~= 0x20001 = 0b10 0000 0000 0000 0001 = 131073~~
~~Storing it in a 16 bit variable drops the 1 at bit 17:~~
~~= 0x0001 = 0b0000 0000 0000 0001 = 1~~
~~```~~
~~Or $1 ≡ 3 \cdot 43691 \mod 65536$ (which would be `1%65536 == 43691%65536` in C).~~
~~This is basically a p-adic/2-adic number with a limited amount of digits. And it is the same as the modular multiplicative inverse with a modulus of 65536 ($2^{16}$).~~
~~This works only with bases that are odd, without any shifting. For this challenge we only print the ones with a numerator of 1.~~
--------
### Rules
~~- Print at least 16 bit of the virtual fraction, you can use more.~~
~~- Print at least the virtual fractions of `1/a` for odd a where `a<98`.~~
- You can print it in any normal base
~~- You can print additional stuff, but it should be clear what parts belong to the virtual fractions and what not.~~
~~- Your program should print the required output in less than 1h on a modern PC (or other hardware that is affordable).~~
--------
### Ungolfed example
```
#!/usr/bin/env python3
#Calculates the modular multiplicative inverse
def imod(a, n):
c=1
while c % a:
c+=n
return c//a
#Print the virtual fractions for 16-bit integers
n=2**16
for i in range(1,98,2): #For the values 1/1, 1/3, ... 1/97
b = imod(i,n)
print("{:>2} * 0x{:>04X} = {:2>} mod 0x{:>04X}".format(i,b,i*b%n,n))
~~```~~

### Goal
Print the modular multiplicative inverse with a modulus of 65536 (or a higher exponent of 2) for odd numbers 1-97.
### Example output
Print this values (or an extension of them):
```
1
43691
52429
28087
36409
35747
20165
61167
61681
51739
53053
14247
23593
55827
49717
31711
33761
44939
7085
28567
39961
48771
20389
18127
22737
64251
21021
46471
60937
55539
38677
61375
4033
19563
4749
43383
61945
51555
14469
5807
18609
17371
64765
60263
18409
12243
54261
23455
41889
```
-------
--------
### Rules
- Use at least a modulus of $65536 = 2^{16}$. But you can use any $ M = 2^N$ for $N ≥ 16$ and $N \in \mathbb{N} $ .
- Print at least the modular multiplicative inverse of for the all natural, odd values $<98$.
- You can print it in any normal base
- You can print additional stuff, but it should be clear what parts belong to the modular multiplicative inverse and what not.
- Your program should print the required output in less than 1 h on a modern PC (or other hardware that is affordable).
--------
### Ungolfed example
```
#!/usr/bin/env python3
#Calculates the modular multiplicative inverse
def imod(a, n):
c=1
while c % a:
c+=n
return c//a
#Print the virtual fractions for 16-bit integers
n=2**16
for i in range(1,98,2): #For the values 1/1, 1/3, ... 1/97
b = imod(i,n)
print("{:>2} * 0x{:>04X} = {:2>} mod 0x{:>04X}".format(i,b,i*b%n,n))
```
-------
### Explanation
You don't have to understand the part in order to participate in the challenge.
There are at least 3 ways to look at this numbers. All lead to the same results. The 2. way is as virtual fractions. virtual fractions are integers that have the feature that you can multiply them with the denominator and you get the numerator when you store them in a N-Bit integer.
For example, you have the 16 bit unsigned integer with the value `0xAAAB` (43691). You can multiply it with 3 and get 1.
```
3 * 0xAAAB = 3 * 0b1010 1010 1010 1011 = 3 * 43691
= 0x20001 = 0b10 0000 0000 0000 0001 = 131073
Storing it in a 16 bit variable drops the 1 at bit 17:
= 0x0001 = 0b0000 0000 0000 0001 = 1
```
This does the following operation: $1 ≡ 3 \cdot 43691 \mod 65536$ (which would be `1%65536 == 43691%65536` or `1&0xFFFF == 43691&0xFFFF` in C). This is interesting because that is what a 16-Bit ALU would do when it multiples `0xAAABu * 3u`.
A 3. way of looking at them is by looking as P-adic numbers. A P-adic number is number, written in base P, that has an infinite amount of digits to the left. And you can add and multiply this values and you get other virtual fractions like you would expect from normal fractions.
In this case it would be a 2-adic number since computer work in binary. And since we have limited amount of memory, we limited this challenge to 16 binary digits, which makes them non-P-adic anymore.

#3: Post edited by

H_H‭ · 2024-01-31T10:23:44Z (3 months ago)

Copy Link

Raw

Markdown

### TL;DR
Print this values (or an extension of them):
```
1
43691
52429
28087
36409
35747
20165
61167
61681
51739
53053
14247
23593
55827
49717
31711
33761
44939
7085
28567
39961
48771
20389
18127
22737
64251
21021
46471
60937
55539
38677
61375
4033
19563
4749
43383
61945
51555
14469
5807
18609
17371
64765
60263
18409
12243
54261
23455
41889
```
------
### Explanation
Virtual fractions are integers that have the feature that you can multiply them with the denominator and you get the numerator when you store them in a N-Bit integer.
For example, you have the 16 bit unsigned integer with the value `0xAAAB` (43691). You can multiply it with 3 and get 1.
```
3 * 0xAAAB = 3 * 0b1010 1010 1010 1011 = 3 * 43691
= 0x20001 = 0b10 0000 0000 0000 0001 = 131073
Storing it in a 16 bit variable drops the 1 at bit 17:
= 0x0001 = 0b0000 0000 0000 0001 = 1
```
~~Or $3 \cdot 43691 = 1 \mod 65536$~~
This is basically a p-adic/2-adic number with a limited amount of digits. And it is the same as the modular multiplicative inverse with a modulus of 65536 ($2^{16}$).
This works only with bases that are odd, without any shifting. For this challenge we only print the ones with a numerator of 1.
-------
### Rules
- Print at least 16 bit of the virtual fraction, you can use more.
- Print at least the virtual fractions of `1/a` for odd a where `a<98`.
- You can print it in any normal base
- You can print additional stuff, but it should be clear what parts belong to the virtual fractions and what not.
- Your program should print the required output in less than 1h on a modern PC (or other hardware that is affordable).
-------
### Ungolfed example
```
#!/usr/bin/env python3
#Calculates the modular multiplicative inverse
def imod(a, n):
c=1
while c % a:
c+=n
return c//a
#Print the virtual fractions for 16-bit integers
n=2**16
for i in range(1,98,2): #For the values 1/1, 1/3, ... 1/97
b = imod(i,n)
print("{:>2} * 0x{:>04X} = {:2>} mod 0x{:>04X}".format(i,b,i*b%n,n))
```

### TL;DR
Print this values (or an extension of them):
```
1
43691
52429
28087
36409
35747
20165
61167
61681
51739
53053
14247
23593
55827
49717
31711
33761
44939
7085
28567
39961
48771
20389
18127
22737
64251
21021
46471
60937
55539
38677
61375
4033
19563
4749
43383
61945
51555
14469
5807
18609
17371
64765
60263
18409
12243
54261
23455
41889
```
------
### Explanation
Virtual fractions are integers that have the feature that you can multiply them with the denominator and you get the numerator when you store them in a N-Bit integer.
For example, you have the 16 bit unsigned integer with the value `0xAAAB` (43691). You can multiply it with 3 and get 1.
```
3 * 0xAAAB = 3 * 0b1010 1010 1010 1011 = 3 * 43691
= 0x20001 = 0b10 0000 0000 0000 0001 = 131073
Storing it in a 16 bit variable drops the 1 at bit 17:
= 0x0001 = 0b0000 0000 0000 0001 = 1
```
Or $1 ≡ 3 \cdot 43691 \mod 65536$ (which would be `1%65536 == 43691%65536` in C).
This is basically a p-adic/2-adic number with a limited amount of digits. And it is the same as the modular multiplicative inverse with a modulus of 65536 ($2^{16}$).
This works only with bases that are odd, without any shifting. For this challenge we only print the ones with a numerator of 1.
-------
### Rules
- Print at least 16 bit of the virtual fraction, you can use more.
- Print at least the virtual fractions of `1/a` for odd a where `a<98`.
- You can print it in any normal base
- You can print additional stuff, but it should be clear what parts belong to the virtual fractions and what not.
- Your program should print the required output in less than 1h on a modern PC (or other hardware that is affordable).
-------
### Ungolfed example
```
#!/usr/bin/env python3
#Calculates the modular multiplicative inverse
def imod(a, n):
c=1
while c % a:
c+=n
return c//a
#Print the virtual fractions for 16-bit integers
n=2**16
for i in range(1,98,2): #For the values 1/1, 1/3, ... 1/97
b = imod(i,n)
print("{:>2} * 0x{:>04X} = {:2>} mod 0x{:>04X}".format(i,b,i*b%n,n))
```

#2: Post edited by

H_H‭ · 2024-01-30T14:56:44Z (3 months ago)

Copy Link

Raw

Markdown

### TL;DR
Print this values (or an extension of them):
```
1
43691
52429
28087
36409
35747
20165
61167
61681
51739
53053
14247
23593
55827
49717
31711
33761
44939
7085
28567
39961
48771
20389
18127
22737
64251
21021
46471
60937
55539
38677
61375
4033
19563
4749
43383
61945
51555
14469
5807
18609
17371
64765
60263
18409
12243
54261
23455
41889
```
------
### Explanation
Virtual fractions are integers that have the feature that you can multiply them with the denominator and you get the numerator when you store them in a N-Bit integer.
For example, you have the 16 bit unsigned integer with the value `0xAAAB` (43691). You can multiply it with 3 and get 1.
```
3 * 0xAAAB = 3 * 0b1010 1010 1010 1011 = 3 * 43691
= 0x20001 = 0b10 0000 0000 0000 0001 = 131073
Storing it in a 16 bit variable drops the 1 at bit 17:
= 0x0001 = 0b0000 0000 0000 0001 = 1
```
Or $3 \cdot 43691 = 1 \mod 65536$
This is basically a p-adic/2-adic number with a limited amount of digits. And it is the same as the modular multiplicative inverse with a modulus of 65536 ($2^{16}$).
This works only with bases that are odd, without any shifting. For this challenge we only print the ones with a numerator of 1.
-------
### Rules
- Print at least 16 bit of the virtual fraction, you can use more.
- Print at least the virtual fractions of `1/a` for odd a where `a<98`.
- You can print it in any normal base
- You can print additional stuff, but it should be clear what parts belong to the virtual fractions and what not.
- Your program should print the required output in less than 1h on a modern PC (or other hardware that is affordable).
-------
### Ungolfed example
```
#!/usr/bin/env python3
~~import sys~~
#Calculates the modular multiplicative inverse
def imod(a, n):
c=1
while c % a:
c+=n
return c//a
#Print the virtual fractions for 16-bit integers
n=2**16
for i in range(1,98,2): #For the values 1/1, 1/3, ... 1/97
b = imod(i,n)
print("{:>2} * 0x{:>04X} = {:2>} mod 0x{:>04X}".format(i,b,i*b%n,n))
```

### TL;DR
Print this values (or an extension of them):
```
1
43691
52429
28087
36409
35747
20165
61167
61681
51739
53053
14247
23593
55827
49717
31711
33761
44939
7085
28567
39961
48771
20389
18127
22737
64251
21021
46471
60937
55539
38677
61375
4033
19563
4749
43383
61945
51555
14469
5807
18609
17371
64765
60263
18409
12243
54261
23455
41889
```
------
### Explanation
Virtual fractions are integers that have the feature that you can multiply them with the denominator and you get the numerator when you store them in a N-Bit integer.
For example, you have the 16 bit unsigned integer with the value `0xAAAB` (43691). You can multiply it with 3 and get 1.
```
3 * 0xAAAB = 3 * 0b1010 1010 1010 1011 = 3 * 43691
= 0x20001 = 0b10 0000 0000 0000 0001 = 131073
Storing it in a 16 bit variable drops the 1 at bit 17:
= 0x0001 = 0b0000 0000 0000 0001 = 1
```
Or $3 \cdot 43691 = 1 \mod 65536$
This is basically a p-adic/2-adic number with a limited amount of digits. And it is the same as the modular multiplicative inverse with a modulus of 65536 ($2^{16}$).
This works only with bases that are odd, without any shifting. For this challenge we only print the ones with a numerator of 1.
-------
### Rules
- Print at least 16 bit of the virtual fraction, you can use more.
- Print at least the virtual fractions of `1/a` for odd a where `a<98`.
- You can print it in any normal base
- You can print additional stuff, but it should be clear what parts belong to the virtual fractions and what not.
- Your program should print the required output in less than 1h on a modern PC (or other hardware that is affordable).
-------
### Ungolfed example
```
#!/usr/bin/env python3
#Calculates the modular multiplicative inverse
def imod(a, n):
c=1
while c % a:
c+=n
return c//a
#Print the virtual fractions for 16-bit integers
n=2**16
for i in range(1,98,2): #For the values 1/1, 1/3, ... 1/97
b = imod(i,n)
print("{:>2} * 0x{:>04X} = {:2>} mod 0x{:>04X}".format(i,b,i*b%n,n))
```

#1: Initial revision by

H_H‭ · 2024-01-30T08:53:44Z (3 months ago)

Copy Link

Raw

Markdown

Print virtual fractions / 2-adic fractions / Modular multiplicative inverse

### TL;DR

Print this values (or an extension of them):
```
1
43691
52429
28087
36409
35747
20165
61167
61681
51739
53053
14247
23593
55827
49717
31711
33761
44939
7085
28567
39961
48771
20389
18127
22737
64251
21021
46471
60937
55539
38677
61375
4033
19563
4749
43383
61945
51555
14469
5807
18609
17371
64765
60263
18409
12243
54261
23455
41889
```


------

### Explanation

Virtual fractions are integers that have the feature that you can multiply them with the denominator and you get the numerator when you store them in a N-Bit integer.

For example, you have the 16 bit unsigned integer with the value `0xAAAB` (43691). You can multiply it with 3 and get 1.

```
  3 * 0xAAAB  =  3 * 0b1010 1010 1010 1011  =  3 * 43691
  =  0x20001  =   0b10 0000 0000 0000 0001  =     131073
Storing it in a 16 bit variable drops the 1 at bit 17:
  =   0x0001  =      0b0000 0000 0000 0001  =          1
```

Or $3 \cdot 43691 = 1 \mod 65536$

This is basically a p-adic/2-adic number with a limited amount of digits. And it is the same as the modular multiplicative inverse with a modulus of 65536 ($2^{16}$).

This works only with bases that are odd, without any shifting. For this challenge we only print the ones with a numerator of 1. 

-------

### Rules

- Print at least 16 bit of the virtual fraction, you can use more.
- Print at least the virtual fractions of `1/a` for odd a where `a<98`.
- You can print it in any normal base
- You can print additional stuff, but it should be clear what parts belong to the virtual fractions and what not.
- Your program should print the required output in less than 1h on a modern PC (or other hardware that is affordable).

-------

### Ungolfed example


```
#!/usr/bin/env python3

import sys 

#Calculates the modular multiplicative inverse
def imod(a, n):
  c=1
  while c % a:
    c+=n
  return c//a

#Print the virtual fractions for 16-bit integers
n=2**16
for i in range(1,98,2): #For the values 1/1, 1/3, ... 1/97
  b = imod(i,n)
  print("{:>2} * 0x{:>04X} = {:2>} mod 0x{:>04X}".format(i,b,i*b%n,n))

```

code-golf math

Communities

Post History