How many bases b are there such that the base b representation of number starts with a 1?

Question

The problem statement is :

Problem Statement-: Altaf has recently learned about number bases and is becoming fascinated.

Altaf learned that for bases greater than ten, new digit symbols need to be introduced, and that the convention is to use the first few letters of the English alphabet. For example, in base 16, the digits are 0123456789ABCDEF. Altaf thought that this is unsustainable; the English alphabet only has 26 letters, so this scheme can only work up to base 36. But this is no problem for Altaf, because Altaf is very creative and can just invent new digit symbols when she needs them. (Altaf is very creative.)

Altaf also noticed that in base two, all positive integers start with the digit 1! However, this is the only base where this is true. So naturally, Altaf wonders: Given some integer N, how many bases b are there such that the base-b representation of N starts with a 1?

Input Format : The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. Each test case consists of one line containing a single integer N (in base ten). Output Format : For each test case, output a single line containing the number of bases b, or INFINITY if there are an infinite number of them. Constraints: 1 <= T <= 10^5 0 <= N < 10^12 Sample Input

 4

 6

 9

 11

 24

Sample Output:

 4

 7

 8

 14

Explanation:

In the first test case, 6 has a leading digit 1 in bases 2, 4, 5 and 6: 610 = 1102 = 124 = 115 = 106.

I trying this in java , But at some point my loop is not working it only takes the first value and after that it will come out of the loop!! Thank you

My code :

import java.util.*;

public class MyClass {
    public static void main(String args[]) {
      
        Scanner sc = new Scanner(System.in);
        long n,i,j,k,m;
        long count=0,rem1,index;
        long rem[];
        rem = new long[(int)100];
        int t = sc.nextInt();
        for(i=1;i<=t;i++)
        {
            
            n = sc.nextInt();
            j=2;
            while(j<=n)
            {

            // for(j=2;j<=n;j++)
            // {
                index=0;
                m = j;
                while(n>0)
                {
                    rem1 = n%m;
                    rem[(int)index++] = rem1;
                    n = (long) (n / m);
                }
                // for(k=index-1;k>=0;k--)
                // {
                    if(rem[1]==1)
                    {
                        count++;
                    }
                // }
                
                j++;
            }
            System.out.println(count);
                            
            // }
        }
        
      
    }
} 

Answer 1

I'm not sure I follow the logic in the loop (and, by your own admission, there's a problem there).

The logic of the loop (i.e., "how many bases represent the number N with a representation starting by 1"), can be greatly simplified.

The first step is finding the highest power of the base B required to represent the number N. This is given by log_b(n), truncated to the nearest integer. Java doesn't have a built-in log function with a variable base, but you can get this result by calculating log(n)/log(b).
Then, you need to find the digit in this position. This can be calculated by dividing N by B^power using integer division.
From there on, you just need to check if the result is 1, and if so, record it.

Put it all together and you'll end up with something like this:

private static int howManyBasesStartWithOne(int num) {
    int count = 0;
    for (int i = 2; i <= num; ++i) {
        int highestBase = (int) (Math.log(num) / Math.log(i));
        int leadingDigit = num / (int) Math.pow(i, highestBase);
        if (leadingDigit == 1) {
            ++count;
        }
    }
    return count;
}