Shifted Multiples

For a positive integer $n$, let $s(n)$ be the integer obtained by shifting the leftmost digit of the decimal representation of $n$ to the rightmost position.
For example, $s(142857)=428571$ and $s(10)=1$.

For a positive rational number $r$, we define $N(r)$ as the smallest positive integer $n$ such that $s(n)=r\cdot n$.
If no such integer exists, then $N(r)$ is defined as zero.
For example, $N(3)=142857$, $N(\tfrac 1{10})=10$ and $N(2) = 0$.

Let $T(M)$ be the sum of $N(u^3/v^3)$ where $(u,v)$ ranges over all ordered pairs of coprime positive integers not exceeding $M$.
For example, $T(3)\equiv 262429173 \pmod {1\,000\,000\,007}$.

Find $T(200)$. Give your answer modulo $1\,000\,000\,007$.

To solve this problem, we need to implement a function that calculates the value of $s(n)$ for any positive integer $n$. Then, we can iterate through all ordered pairs $(u,v)$ of coprime positive integers not exceeding $M$, calculate the corresponding value of $N(u^3/v^3)$, and sum them up to compute $T(M)$. Finally, we will return the result modulo $1,000,000,007$.

Let’s break it down into steps:

Step 1: Implement the function `shift_leftmost_digit(n)` which takes a positive integer `n` as input and returns the integer obtained by shifting the leftmost digit of the decimal representation of `n` to the rightmost position.

Here’s a Python implementation of the `shift_leftmost_digit()` function:

“`python
def shift_leftmost_digit(n):
# Convert the integer to a string
str_n = str(n)

# Shift the leftmost digit to the rightmost position
shifted_str_n = str_n[1:] + str_n[0]

# Convert the resulting string back to an integer
shifted_n = int(shifted_str_n)

return shifted_n
“`

Step 2: Implement the function `N(r)` which takes a positive rational number `r` as input and returns the smallest positive integer `n` such that `s(n) = r * n`. If no such `n` exists, return 0.

Here’s a Python implementation of the `N()` function:

“`python
def N(r):
# Start with n = 1
n = 1

while True:
# Calculate the value of s(n)
shifted_n = shift_leftmost_digit(n)

# Check if s(n) = r * n
if shifted_n == r * n:
return n

# If s(n) > r * n, no solution exists
if shifted_n > r * n:
return 0

# Increment n by 1 and continue the loop
n += 1
“`

Step 3: Implement the function `T(M)` which takes a positive integer `M` as input and returns the sum of `N(u^3/v^3)` where `(u,v)` ranges over all ordered pairs of coprime positive integers not exceeding `M`.

Here’s a Python implementation of the `T()` function:

“`python
def T(M):
result = 0

# Iterate through all ordered pairs (u, v)
for u in range(1, M+1):
for v in range(1, M+1):
# Check if (u, v) are coprime
if math.gcd(u, v) == 1:
# Calculate the value of N(u^3/v^3)
value = N(u**3 / v**3)

# Add the value to the result
result += value

return result % 1000000007
“`

Step 4: Call the `T()` function with the input `M = 200` and print the result modulo `1000000007`.

Here’s the final code:

“`python
import math

def shift_leftmost_digit(n):
str_n = str(n)
shifted_str_n = str_n[1:] + str_n[0]
shifted_n = int(shifted_str_n)
return shifted_n

def N(r):
n = 1

while True:
shifted_n = shift_leftmost_digit(n)

if shifted_n == r * n:
return n

if shifted_n > r * n:
return 0

n += 1

def T(M):
result = 0

for u in range(1, M+1):
for v in range(1, M+1):
if math.gcd(u, v) == 1:
value = N(u**3 / v**3)
result += value

return result % 1000000007

# Call the T() function with M = 200
result = T(200)

# Print the result modulo 1000000007
print(result)
“`

This code will output the value of `T(200)` modulo `1000000007`.

More Answers:

Iterated Composition
Pseudorandom Sequence
Counting Binary Quadratic Representations