Review Suggested Edit

You can't approve or reject suggested edits because you haven't yet earned the Edit Posts ability.

Print virtual fractions / 2-adic fractions / Modular multiplicative inverse [FINALIZED]

~~## Now posted: [Print virtual fractions / 2-adic fractions / Modular multiplicative inverse](https://codegolf.codidact.com/posts/290612)~~
---
### 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.
-------
### 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))
```

## Now posted: [Print virtual fractions / 2-adic fractions / Modular multiplicative inverse](https://codegolf.codidact.com/posts/290667)
---
### 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.
-------
### 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 finalized

Communities

Review Suggested Edit