All the buzzkill for just one number

Computer Science Level 5

I have a $10$ digit number in mind, you can obtain the digits of the number from left to right by following the five points below.

$\bullet$ The $3^{\text{rd}}$ smallest positive integer which has square root of the sum of all its quadratic residues equal to $\frac{1}{3}$ of the integer itself, gives first $2$ digits of my number.

$\bullet$ If $489$ people are sitting around a table, everyone given numbers $1$ to $489$ clockwise (counting starts from number $1$ ) and then every $13^{\text{th}}$ person is asked to get out. The only remaining person's number gives next $3$ digits of my number. In other words, find $\text{josephus}(489,13)$ .

$\bullet$ The $7^{\text{th}}$ largest positive integer which has, out of all positive integers less than itself, exactly $60$ coprime to itself, gives next $2$ digits of my number. In other words, find the seventh largest $n$ such that $\text{phi}(n)=60$

$\bullet$ The only prime number which has exactly $27$ quadratic residues gives next $2$ digits of my number

$\bullet$ The last digit of my number is $0$

What is my number?

Details and assumptions :

$\bigotimes$ This problem May seem boring because it's long, but will feel awesome after solving. Everything in this problem has a meaning, nothing is a troll.

$\bigotimes$ Quadratic residues of a number $n$ are the possible remainders when square of any integer is divided by $n$ .

For example, any square integer can give remainder only from $(0,1,4,5,6,9)$ when divided by $10$ , so $10$ has six quadratic residues and their sum is $0+1+4+5+6+9=25$

$\bigotimes$ Here are links, if you want clarification regarding concepts used in the problem.

Josephus Problem
Euler totient function : $\phi$
Quadratic Residues

Concept of many problems in one, adapted from Pi Han Goh's Buzzkill

The answer is 9922793530.

3 solutions

Aditya Raut
Mar 23, 2015

Here are python programs for things i used in this problem-

Josephus problem (Returns a number)

def josephus(n, r):
    t = 0
    i = 1
    while i <= n:
        t = (t + r) % i
        i += 1
    return t + 1

Euler's Totient Function , or phi $\phi$ (Returns a number)

from fractions import gcd
def phi(n):
    list=[]
    for i in range(n):
        if gcd(n,i)==1:
            list.append(i)
    return len(list)

Quadratic Residues (Returns list of quadratic residues)

def quad_residue(n):
    li=[]
    for i in range(n):
        li.append(i*i%n)
    b=set(li)
    li=list(b)
    return li

Prime numbers (Returns list of prime numbers till 'a')

def primes(n):
     list=[]
     for  a in range(n):
               if not ( a < 2 or any(a % i == 0 for i in range(2, int(a ** 0.5) + 1))) is True:
                 list.append(a)
     return list

As asked in the problem, here's point by point solution of the 5 bullet point conditions.

import math
for i in range(1,100):
        if math.sqrt(sum(quad_residue(i)))==i/float(3): 
                       print i
3
45
99
>>>

Hence needed number is $\boxed{99}$

1 2	`josephus(489,13) 227`

Hence next 3 digits are $\boxed{227}$

for i in range(1000):
       if phi(i)==60:
           print i
61
77
93
99
122
124
154
186
198

Hence 7th largest number with phi(n)=60 is $\boxed{93}$

for i in primes(1000):
      if len(quad_residue(i))==27:
          print i
53

Hence the next 2 digits are $\boxed{53}$ . Last digit is 0, given.

Hence the 10-digit number is $\boxed{9922793530}$

@Agnishom Chattopadhyay , @Pranjal Jain , @Raghav Vaidyanathan .... Long but interesting!