index

Recursive numbers

The task.

Find such a 10-digit number, in which the first digit is equal to the amount of zeros in this number. The second digit is equal to the amount of units in this number, and so on. The tenth digit equals to the amount of nines in this number.

For example, the number 6 210 001 000 . It has 6 zeros, 2 units, 1 digit two, 1 digit six. There is no other digits.

The task is extended for n-digit numbers.

The answer to this task is quite curious.

n =2 - no solutions,

n = 3 - no solutions,

n = 4 - two solutions - 1210 and 2020,

n = 5 - one solution - 21200,

n = 6 - no solutions,

n = 7 - one solution - 3211000,

n > 7 - one solution -

n-4 , 2 , 1 , 0 , ... , 0 , 1 , 0 , 0 , 0 .

We solve the task through the supercompiler.

The source Java-program:

class RecNumb {
    public static final int nofDigits = 5;

    static class State {
        int[] digits = new int[nofDigits];

        State (int[] digits) {
            for (int i=0; i<nofDigits; i++) {
                this.digits[i] = digits[i];
            }
        }
    }

    public static void main (String args[]) throws Exception {
        int[] digits = { 2, 1, 2, 0, 0};
        checkAndPrint (digits);
    }

    public static void checkAndPrint(int[] digits1) throws Exception {
        int[] digits = new int[nofDigits];

        for (int i=0; i<nofDigits; i++) {
            digits[i] = digits1[i];
        }  

        State s = new State (digits);

        for (int i=0; i<nofDigits; i++) {
            int sum = iDigit(s, i);
            for (int j=0; j<nofDigits; j++) {
                if(iDigit(s, j)==i) sum--;
                if(sum<0) throw new Exception();
            }
            if(sum>0) throw new Exception();
        }
        
        String out = "";
        for (int i=0; i<nofDigits; i++) out = out + s.digits[i];
        System.out.println(out);
    }

    public static int iDigit(State s, int ia) throws Exception {
        for (int i=0; i<nofDigits; i++) {
            if (s.digits[ia]==i) {s.digits[ia]=i; return i;}
        }
        throw new Exception();
    }

nofDigits - sets a length of numbers in the example.

The array int [] digits is for the testing.

Here I shall give small residual programs.

nofDigits = 2 (no solutions)

 
public static void checkAndPrint (final int[] digits1_1)
	  throws java.lang.Exception
	{
	  final int[] digits_2 = new int[2];
	  final int digits1_0_3 = digits1_1[0];
	  digits_2[0] = digits1_0_3;
	  final int digits1_1_6 = digits1_1[1];
	  digits_2[1] = digits1_1_6;
	  final int[] digits_14 = new int[2];
	  digits_14[0] = digits1_0_3;
	  digits_14[1] = digits1_1_6;
	  throw new java.lang.Exception();
	}
//---------------------------   0 sec - JScp version 0.1.22

nofDigits = 3 (no solutions)

 
public static void checkAndPrint (final int[] digits1_1)
	  throws java.lang.Exception
	{
	  final int[] digits_2 = new int[3];
	  final int digits1_0_3 = digits1_1[0];
	  digits_2[0] = digits1_0_3;
	  final int digits1_1_6 = digits1_1[1];
	  digits_2[1] = digits1_1_6;
	  final int digits1_2_9 = digits1_1[2];
	  digits_2[2] = digits1_2_9;
	  final int[] digits_18 = new int[3];
	  digits_18[0] = digits1_0_3;
	  digits_18[1] = digits1_1_6;
	  digits_18[2] = digits1_2_9;
	  throw new java.lang.Exception();
	}
//---------------------   1 sec - JScp version 0.1.22

nofDigits = 4 (two solutions)

 
public static void checkAndPrint (final int[] digits1_1)
	  throws java.lang.Exception
	{
	  final int[] digits_2 = new int[4];
	  final int digits1_0_3 = digits1_1[0];
	  digits_2[0] = digits1_0_3;
	  final int digits1_1_6 = digits1_1[1];
	  digits_2[1] = digits1_1_6;
	  final int digits1_2_9 = digits1_1[2];
	  digits_2[2] = digits1_2_9;
	  final int digits1_3_12 = digits1_1[3];
	  digits_2[3] = digits1_3_12;
	  final int[] digits_22 = new int[4];
	  digits_22[0] = digits1_0_3;
	  digits_22[1] = digits1_1_6;
	  digits_22[2] = digits1_2_9;
	  digits_22[3] = digits1_3_12;
	  if (digits1_0_3 == 0) {
	    throw new java.lang.Exception();}
	  if (digits1_0_3 == 1) {
	    if (digits1_1_6 == 0
	    ||  digits1_1_6 == 1
	    ||  digits1_1_6 != 2
	    ||  digits1_2_9 == 0
	    ||  digits1_2_9 != 1
	    ||  digits1_3_12 != 0) {
	      throw new java.lang.Exception();}
	    java.lang.System.out.println("1210") /*virtual*/;}
	  else {
	    if (digits1_0_3 != 2
	    ||  digits1_1_6 != 0
	    ||  digits1_2_9 == 0
	    ||  digits1_2_9 == 1
	    ||  digits1_2_9 != 2
	    ||  digits1_3_12 != 0) {
	      throw new java.lang.Exception();}
	    java.lang.System.out.println("2020") /*virtual*/;}
	  return;
	}
//--------------------------------   6 sec - JScp version 0.1.22

nofDigits = 5 (one solution)

 
public static void checkAndPrint (final int[] digits1_1)
	  throws java.lang.Exception
	{
	  final int[] digits_2 = new int[5];
	  final int digits1_0_3 = digits1_1[0];
	  digits_2[0] = digits1_0_3;
	  final int digits1_1_6 = digits1_1[1];
	  digits_2[1] = digits1_1_6;
	  final int digits1_2_9 = digits1_1[2];
	  digits_2[2] = digits1_2_9;
	  final int digits1_3_12 = digits1_1[3];
	  digits_2[3] = digits1_3_12;
	  final int digits1_4_15 = digits1_1[4];
	  digits_2[4] = digits1_4_15;
	  final int[] digits_26 = new int[5];
	  digits_26[0] = digits1_0_3;
	  digits_26[1] = digits1_1_6;
	  digits_26[2] = digits1_2_9;
	  digits_26[3] = digits1_3_12;
	  digits_26[4] = digits1_4_15;
	  if (digits1_0_3 == 0
	  ||  digits1_0_3 == 1
	  ||  digits1_0_3 != 2
	  ||  digits1_1_6 == 0
	  ||  digits1_1_6 != 1
	  ||  digits1_2_9 == 0
	  ||  digits1_2_9 == 1
	  ||  digits1_2_9 != 2
	  ||  digits1_3_12 != 0
	  ||  digits1_4_15 != 0) {
	    throw new java.lang.Exception();}
	  java.lang.System.out.println("21200") /*virtual*/;
	  return;
	}
//------------------------------- 135 sec - JScp version 0.1.22

The time of supercompilation is enlarged. Thus the experiments were cancelled.

The scheme of mathematical solution

Let a0, a1..., an are digits of a required n+1-digit number. The count of the amount of digits by different ways gives two relations

a0 + a1 +... + an = n+1

0*a0 + 1*a1 + 2*a2 +... + n*an = n+1

Further there goes a search of variants taking into acount plenties of zeros.