Reversed Multiples

Computer Science Level 4

Let the reverse of a positive integer $n$ , denoted $R(n),$ be the result when the digits of the number are written backwards; for example, $R(190) = 091,$ or just $91.$

Call a positive integer $n$ brilliant if $n + R(n)$

is a multiple of 13. Let $B$ be the $10000$ th brilliant number. Compute the last three digits of $B.$

The answer is 241.

21 solutions

Santanu Banerjee
Dec 15, 2013

I did using the following java code:

import java.io.*;
import java.math.*;
public class ReversedMultiples

{
    public static void main(String args[])
    {
        ReversedMultiples obj=new ReversedMultiples();
        long d=0,k=0,i=0;
        for(i=1;;i++)
        {
            d=i+obj.Rev(i);
            if(d%13==0)
            {   
                k++;
                if(k==10000)
                    break;
            }
        }
        System.out.println(i);
    }
    long Rev(long a)
    {
        long h=0;
        while(a!=0)
        {
            h=(h*10)+(a%10);
            a/=10;
        }
        return h;
    }
}

Python:

count=0
for i in range (1,15000):
    y=int(str(i)[::-1])
    if (i+y)%13==0:
        count+=1
        print count,i

The three digit number 10000 will be print $130\fbox{241}$

pebrudal zanu - 7 years, 4 months ago

Hmm, why do you need the

import java.io.*

Michael Tang - 7 years, 5 months ago

These are java inbuilt classes "io" refers to inputoutput if you dont use it u cant use the print statement

Moreover I only know C and Java, I don't know Python so cant understand anything above except part of the logic

Santanu Banerjee - 7 years, 5 months ago

No, you definitely don't need that import; you've already sufficiently qualified the method when you type System.out.println(), because System comes from java.lang.System which is automatically imported into every program.

Limao Luo - 7 years, 5 months ago

Well, Santanu I too did it using Java but I didn't import the the I/O package since I don't think there will be any need of it. Also java.math package isn't required.

Soham Dibyachintan - 7 years, 5 months ago

Here 's my C++ solution.

Prasun Biswas - 5 years, 10 months ago

String handling functions for reversing along with Standard library functions like atoi and itoa considerably reduce that code to 7-8 lines.

Kunal Verma - 5 years, 1 month ago

I started learning Haskell a few weeks ago and it turns out there's a really simple one-liner Haskell solution to this problem. Since no one posted a Haskell solution here, I'm posting it as a comment here:

1	`main = print (rem ([n\|n<-[1..],rem (n+read ((reverse.show) n) :: Int) 13 == 0]!!9999) 1000)`

Prasun Biswas - 5 years, 1 month ago

Zeeshan Ali
Feb 5, 2016

The amazing fact, I found, in such brilliant numbers $i$ is that most of the $i+R(i)$ are palindromes :)

Oliver Welsh
Dec 15, 2013

Python solution:

    def r(n):
        return int(str(n)[::-1])

    def brilliant(n):
        return (n + r(n)) % 13 == 0

    def calculate_n_brilliant(n):
        total = 0
        i = 0

        while total < n:
            i += 1
            if brilliant(i):
                total += 1

        return i

    print(calculate_n_brilliant(10000))

Can you provide any insight into the classification of brilliant numbers?

Calvin Lin Staff - 7 years, 5 months ago

2-digits: If $n=\underline{ab}=10a+b$ is brilliant, then $n+r(n)=11a+11b=11(a+b)$ must be divisible by 13, so the sum of the digits must be equal to 13.

3-digits: If $n=\underline{abc}=100a+10b+c$ is brilliant, then $n+r(n)=101a+20b+101c$ is divisible by 13. Taking mod 13, we have $10a+7b+10c$ is divisible by 13.

Anybody want to generalise? (Or does there even exist such a generalisation)

minimario minimario - 7 years, 5 months ago

Let $n = \overline{a_da_{d-1}a_{d-2}\dots a_2a_1a_0}.$

Then $n + R(n) = \sum_{k=0}^d (10^k + 10^{d-k}) a_k) =: \sum_{k=0}^d f_{d,k} a_k.$ To determine whether a number is "brilliant" we only need to know the $f_{d,k}$ modulo 13. Here is a table (where each $f_{d,k}$ is reduced to a remainder between $-6$ and $6$ ):

$\begin{array}{r|cccccccccc} d, k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline 0 & 2 \\ 1 & -2 & -2 \\ 2 & -3 & -6 & -3 \\ 3 & 0 & 6 & 6 & 0 \\ 4 & 4 & -4 & 5 & -4 & 1 \\ 5 & 5 & 0 & -5 & -5 & 0 & 5 \\ 6 & 2 & 1 & -1 & -2 & -1 & 1 & 2 \\ 7 & -2 & -2 & 0 & 2 & 2 & 0 & -2 & -2 \\ 8 & -3 & -6 & -3 & 3 & 6 & 3 & -3 & -6 & -3 \\ 9 & 0 & 6 & 6 & 0 & -6 & -6 & 0 & 6 & 6 & 0 \\ \end{array}$

In fact, each of the rows in the table may be multiplied or divided by a factor $\not\equiv\ 0$ mod 13. For instance, we can simplify to

$\begin{array}{r|cccccccccc} d, k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline 0 & 1 \\ 1 & 1 & 1 \\ 2 & 1 & 2 & 1 \\ 3 & 0 & 1 & 1 & 0 \\ 4 & -1 & 1 & 2 & 1 & -1 \\ 5 & 1 & 0 & -1 & -1 & 0 & 1 \\ 6 & 2 & 1 & -1 & -2 & -1 & 1 & 2 \\ 7 & 1 & 1 & 0 & -1 & -1 & 0 & 1 & 1 \\ 8 & 1 & 2 & 1 & -1 & -2 & -1 & 1 & 2 & 1 \\ 9 & 0 & 1 & 1 & 0 & -1 & -1 & 0 & 1 & 1 & 0 \\ \end{array}$

For example, a ten-digit number is brilliant if $13 | (a_1 + a_2 - a_4 - a_5 + a_7 + a_8).$

There is obviously some symmetry in the table. Each row is naturally its own reverse. Also, each row repeats itself with period six. This has to do with the fact that $10^6 \equiv 1$ mod 13. It follows that $f_{d,k+6} = 10^{k+6} + 10^{d-k-6} \equiv 10^k + 10^{d-k} = f_{d,k}.$ Also, there is also a repetition of period six in the columns: $f_{d+6,k} = 10^k + 10^{d+6-k} \equiv 10^k + 10^{d-k} = f_{d,k}$

$\begin{array}{r|cccccc|} d',k' & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline 0 & 2 & 1 & -1 & -2 & -1 & 1 \\ 1 & 1 & 1 & 0 & -1 & -1 & 0 \\ 2 & 1 & 2 & 1 & -1 & -2 & -1 \\ 3 & 0 & 1 & 1 & 0 & -1 & -1 \\ 4 & -1 & 1 & 2 & 1 & -1 & -2 \\ 5 & 1 & 0 & -1 & -1 & 0 & 1 \\ \hline \end{array}$

For a number with $d+1$ digits, the coefficient of digit $a_k$ is the value in the table at $(d',k') = (d\ \text{mod}\ 6, k\ \text{mod}\ 6)$ .

Final example: if 130241 brilliant?

Yes, because (according to row 5 of the table, read right-to-left) $1\cdot 1 + 0\cdot 4 + (-1)\cdot 2 + (-1)\cdot 0 + 0\cdot 3 + 1\cdot 1 = 1-2+1 = 0$ is a multiple of 13.

Arjen Vreugdenhil - 5 years, 6 months ago

I didn't make the problem with any sort of mathematical meaning in mind, but perhaps Calvin knows something we don't...?

Michael Tang - 7 years, 5 months ago

Good job! I love python because the r(n) function is so simple - in Java (AFAIK) you need at least 4 lines!

Michael Tang - 7 years, 5 months ago

Arjen Vreugdenhil
Nov 18, 2015

Here is my creative solution :)

int count = 0;
int d = 0;
int a[] = { 0, 0, 0, 0, 0, 0, 0, 0 };
int f[][] = { {2}, {-2,-2}, {-3,-6,-3}, {0,6,6,0}, {4,-4,5,-4,4}, {5,0,-5,-5,0,5} };
int rem = 0;

while (count < 10000) {
    int i;
    for (i = 0; i <= d; i++) {
       a[i]++; rem += f[d][i]; 
       if (a[i] < 10) break;
       a[i] = 0; rem -= f[d][i]*10;
    }
    if (i > d) { d++; a[d] = 1; rem = f[d][d]; }

    if (rem % 13 == 0) count++;
}

for (int j = 2; j >= 0; j--) out.print(a[j]); out.println();

Explanation: If the number has $d+1$ digits then $n + R(n) = (10^d + 1)a_0 + (10^{d-1} + 10)a_1 + (10^{d-2} + 100)a_2 + \cdots + (1 + 10^d)a_d.$ We write this as $n + R(n) \equiv f_{d,0}a_0 + f_{d,1}a_1 + f_{d,2}a_2 + \cdots + f_{d,d}a_d\ \ \text{mod}\ 13.$ The table of $f$ s is pre-programmed. Numbers are generated by increasing digits and updating the variable $rem \equiv n+R(n)$ mod 13.

Output: $\boxed{241}$ .

As for run-time, the computer reported 0 milliseconds. When I extended the program to include the first 100,000 brilliant numbers, it was 15 ms.

Arjen Vreugdenhil - 5 years, 6 months ago

Jafar Badour
Oct 9, 2015

// ConsoleApplication106.cpp : Defines the entry point for the console application.
// JB


#include "stdafx.h"
#include<iostream>
#include<cmath>
using namespace std;

int main(){

    int x=0;
    int you=0;
    int alla = 0;
    while (true){
        x = you;

        int f;
        int z = 0;
        int i = 0;
        int b = 0;
        int g = x;
        //cout << x << "\n";
        while (true){

            x = x / 10;
            if (x == 0)break;
            b++;
        }
        x = g;
        while (true){
            f = x % 10;
            x = x / 10;
            z = z + f*pow(10, b - i);
            i++;
            if (x == 0)break;


        }
        //cout << "\t" << z+you << "\n";
        if ((z+you) % 13 == 0)alla++;
        if (alla >10000){
            cout << "u" << you << "\n";

            break;
        }

        you++;
    }


}

output

130241!

Samarpit Swain
Sep 21, 2015

#include <iostream>
using namespace std;

int main() {

     unsigned long int num,dig,Rn,count=0;

for(unsigned long int x=1;x<=10000000;x++)
    {       Rn=0;
          num=x;

           while(num>0)

           { dig=num%10;
               Rn=(10*Rn)+dig;
               num/=10;
           }

  if((x+Rn)%13==0)
          count++;
     if(count==10000)
       { cout<<x;
                break;}

    }
    return 0;
}

Output:

David Holcer
Mar 20, 2015

array=[]
num=1
enough=False
while not enough:
    if (num+int(str(num)[::-1]))%13==0:
        array.append(num)
    if len(array)==10000:
        enough=True
    num+=1
print str(array[9999])[-3:]

Claus-Dieter Volko
Feb 2, 2014

This is also a rather easy problem, but it needs a clarification: Sometimes zero is considered a positive integer; however, this assumption must not be made here, as the result will then be deemed erroneous. In this task, 1 is the first positive integer. With this assumption, the result will be accepted. Here's my code in C++.

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>

    const int string_len = 100;

    int reverse (int number)
    {
      char string[string_len];
      char string_new[string_len];

      itoa (number, string, 10);

      int current_len = strlen(string);
      for (int i = 0; i < current_len; i++)
        string_new[i] = string[current_len - 1 - i];
      string_new[current_len] = '\0';

      return atoi (string_new);
    }

    void main ()
    {
      int count = 0;
      int number = 1;

      while (count < 10000)
      {
        if ((number + reverse (number)) % 13 == 0)
        {
          count++;
          printf ("%d ", number);
        }
        number++;
      }

      printf ("\nThe 10000th brilliant number is: %d", number - 1);
    }

Just curious - is there any standard reference or text where 0 is considered positive? I've heard of differing conventions on the "natural numbers" (with or without 0) but never that 0 could be a "positive integer". Thanks!

Sendhil Revuluri - 6 years, 9 months ago

The problem with itoa(); is that it's not standard. Many compilers like G++ doesn't support it. It's best to avoid using it. You can formulate a simpler solution by making your own reverse function by using basic math.h functions. If you wish, you can see my solution in C++ (although, this can be made shorter).

Prasun Biswas - 5 years, 10 months ago

Rakha Kautsar
Jan 10, 2014

Here's a ruby solution:

def r(n)
    return n.to_s.reverse.to_i
end

def main()
    i=0
    n=0
    while i<10000 do
        n=n+1
        if((n+r(n)) % 13 == 0)
            i=i+1
        end
    end
    puts n
end

main()

Carl Denton
Dec 27, 2013

Solution in Java. Runtime of 100-110 ms.

public class ReversedMultiples
{
public static void main(String[] args)
{
    long startTime = System.currentTimeMillis();
    int brillNum = 0;
    long last = 0;
    for (long i = 13; brillNum < 10000; i++)
    {
        if (isBrilliant("" + i))
        {
            brillNum++;
        }
        if (brillNum == 10000)
            last = i;
    }
    System.out.println("10000th brill num: " + last);
    long endTime = System.currentTimeMillis();
    long elapsedTime = endTime - startTime;
    System.out.println("Runtime: " + elapsedTime + " ms");
}
public static boolean isBrilliant(String n)
{
    char[] array = new char[n.length()];
    for (int i = 0; i < n.length(); i++)
    {
        array[i] = n.charAt(n.length() - i - 1);
    }
    String output = new String(array); 
    return ((Integer.parseInt(n) + Integer.parseInt(output)) % 13 == 0);
}
}

Output:

10000th brill num: 130241 
Runtime: 98 ms

Jubayer Nirjhor
Dec 15, 2013

Python Solution

    def reverse(m):
        listed = [str(i) for i in str(m)]
        reversed_list = listed[::-1]
        string_form = ''.join(reversed_list)
        integer_form = int(string_form)
        return integer_form

    brilliant_finder = 0

    for n in range (1, 1000000):
        if (n + reverse(n)) % 13 == 0:
            brilliant_finder += 1
            if brilliant_finder == 10000:
                print n

Output: $130\fbox{241}$

Jubayer Nirjhor - 7 years, 5 months ago

Here is a code snippet in C# that does the work...

           // Reversed Multiples
           int cn = 0;
           int lc = 0;
           while (true)
           {
               lc += 1;
               char[] a = lc.ToString().ToCharArray();
               string xa = new string(a.Reverse().ToArray());

               if (((lc + double.Parse(xa)) % 13) == 0)
               {
                   cn += 1;
                   if (cn == 10000) break;
               }
           }
           MessageBox.Show(lc.ToString());

Sanjay kamath - 7 years, 3 months ago

B P
Nov 26, 2017

C implementation without strings.

#include <stdio.h>
#include <inttypes.h>

uint64_t r(uint64_t x) {
    uint64_t ans = 0;   
    while (x > 0) {
        ans = ans*10 + (x%10);
        x /= 10;
    }   
    return ans;
}

int main(void) {
    uint64_t n = 0;
    for (int i = 10000; i > 0;) {
        n++;
        if ((n + r(n)) % 13 == 0) i--;
    }
    printf("the 10000th brilliant number: %" PRIu64 "\n", n);
    return 0;
}

Jesse Nieminen
Feb 16, 2017

The following Python code solves the problem:

n, c = 0, 0
while c < 10000:
    n += 1
    k = n + int(str(n)[::-1])
    c += 1 if k % 13 == 0 else 0
print(n % 1000)

Hence, the answer is $\boxed{241}$

Jim Clark
Jan 30, 2017

My perl solution:

my $num=1;
my @brilliants = ();
while ( scalar @brilliants < 10000 ) {
  my $revnum = reverse $num;
  my $potbrill = $num + $revnum;
  if ( $potbrill % 13 == 0 ) {
    push @brilliants, $num;
  }
  $num ++;
}
print "10000th: $brilliants[9999]\n";

Rushikesh Jogdand
Jun 30, 2016

def is_brilliant(n):
    return (int(str(n)[::-1])+n)%13==0
count=0
number=1
while count<10000:
    if is_brilliant(number):
        count+=1
    number+=1
print(number-1)

Mark Anastos
May 19, 2016

In Haskell:

(`mod` 1000) $ (!!9999) $ filter (\n -> (n + rev n) `mod` 13 == 0) [1..]
    where rev = read . reverse . show :: Int -> Int

Hjalmar Orellana Soto
Feb 20, 2016

def R(a):
_q=len(str(a))-1
_w=""
_while q>=0:
_ _ w=w+str(a)[q]
_ _ q-=1
_return int(w)
n=0
a=0
while n<10000:
_a+=1
_if (a+R(a))%13==0:
_ _ n+=1
print a

Akshit Soota
Feb 22, 2014

If you are using VB.NET, you could try this:

Sub Main()
    Dim bnos(10001) As Integer
    Dim ctr As Integer = 0
    Dim no As Integer = 0
    Dim rno As Integer
    While ctr <> 10001
        no = no + 1
        rno = Integer.Parse(StrReverse(no.ToString()))
        If (no + rno) Mod 13 = 0 Then
            bnos(ctr) = no
            ctr = ctr + 1
        End If
    End While
    Console.WriteLine(bnos(9999))
    Console.ReadLine()
End Sub

Yash Mittal
Jan 22, 2014

Below is a Python Code for the question.

def ans(n):
    count=0
    i=1  
    while i<n:
        if (i + int(str(i)[ ::-1])) % 13 == 0:
            count = count + 1
        if count == 10000:
            return i, count
        i=i+1
print ans(1000000)

This will give you $\boxed{130241}$ in the last line of output. Please be patient; use this Python Interpreter . Hope it helped!

Nikhil Tyagi
Dec 18, 2013

Python is like this One :

def rev(x) : x = str(x) x = x[ : :-1] x = int(x) return x n = 0 for i in range(1,1000000): if (i + rev(i))%13 == 0 : n += 1 if n == 10000 : print i

see the first observation.

Stefan Stankovic
Dec 16, 2013

Solution in Mathematica:

In[1]:= R[n_] := FromDigits@Reverse@IntegerDigits@n;

Select[Range[1000000], ((R[#] + #)~Mod~13 == 0) &][[10000]]

Out[2]= 130241

The APL way: APL i←⍳1000000 ⋄ n←0=13∣i+10⊥¨⌽¨((⌈¨10⍟i+1)⎕repl ¨10)⊤¨i ⋄ 10000⊃n/i 130241

Better APL way:

APL

∇ ret←Reverse rarg

[1] ret←10⊥⌽((⌈10⍟rarg+1)/10)⊤rarg

∇

10000⊃Where 0= 13∣ (⍳200000)+Reverse¨ ⍳200000

130241

:-)

Apl Way - 5 years, 10 months ago

Reversed Multiples

The answer is 241.

21 solutions

0 pending reports