4 replies to this topic

[puuhikki]

I'm relatively newcomer on programming as I'm educated a mathematician and have no experience on Python. I would like to know how to solve this problem in Python which appeared as I was studying one maths problem on my own:

Program asks a positive integer m. If m is of the form 2^n-1 it returns T(m)=n*2^{n-1}. Otherwise it writes m to the form 2^n+x, where -1<x<2^n, and returns T(m)=T(2^n-1)+x+1+T(x). Finally it outputs the answer.

[CatatonicMan]

Is the sequence guaranteed to end?

[puuhikki]

Well, actually I was doing a little bit research on maths. I managed to solve the problem I wanted to so this question is not of current interest anymore.

[Somelauw]

puuhikki said:

Program asks a positive integer m. If m is of the form 2^n-1 it returns T(m)=n*2^{n-1}.

from math import log
if log(m + 1, 2) % 1 == 0

Quote

Otherwise it writes m to the form 2^n+x, where -1<x<2^n, and returns T(m)=T(2^n-1)+x+1+T(x). Finally it outputs the answer.

You can probably bruteforce this with a forloop. I don't really understand the equation.
It seems logical to make x positive and as small as possible.

Quote

Well, actually I was doing a little bit research on maths. I managed to solve the problem I wanted to so this question is not of current interest anymore.

It would be nice if you posted that solution.

Edited by Somelauw, 16 June 2010 - 10:24 AM.

[puuhikki]

I solved the problem by Java as I'm more familiar with that. Here is an ugly code which works in most of the cases but sometimes it won't work, for example if input is 8.

import java.math.BigInteger;


public class BigInt {

  public static void main(String[] args) {

    BigInteger luku = new BigInteger ("2");

    boolean potenssi=ispowertwo(luku);

    if (potenssi==false) {

// Find m and x such that luku=2^m+x where -1<x<2^m.

   int m=maxpow(luku);

//      System.out.println(luku*pow(2^(luku-1));

   BigInteger x = new BigInteger("1");

        x=luku.subtract(((new BigInteger ("2")).pow(m)));

        System.out.println("T("+luku+")=T(2^"+m+"+"+x+")");

   BigInteger y = x.add(new BigInteger("1"));

   System.out.println("T("+luku+")="+m+"*2^"+(m-1)+"+"+y+"+T("+x+")");

   BigInteger z = (new BigInteger ("2")).pow(m-1);

   System.out.println("2^"+(m-1)+"="+z);

   BigInteger w = BigInteger.valueOf(m).multiply(z);

   System.out.println((m)+"*2^"+(m-1)+"="+w);

   BigInteger t = w.add(y);

   System.out.println("T("+luku+")="+t+"+T("+x+")");

//T(2^n+x)=n*2^{n-1}+x+1+T(x)

    }

    else {

      // The number is of the form 2^n-1 so return n*2^{n-1}.

   System.out.println("Power!");

    }

  }


// Checks if the number is of the form 2^m-1 for some integer m.

  public static boolean ispowertwo(BigInteger n) {

    BigInteger testi = new BigInteger ("1");

    while (testi.compareTo(n)==-1) {

      testi=testi.multiply(new BigInteger ("2"));

//      System.out.println(testi);

    }

    if (testi.compareTo(new BigInteger("1").add(n))==0) return true;

    return false;

  }


// Checks if the number is of the form 2^m-1 for some integer m.

  public static int maxpow(BigInteger n) {

    BigInteger testi = new BigInteger ("1");

    int pow=0;

    while (testi.compareTo(n)==-1) {

      testi=testi.multiply(new BigInteger ("2"));

      ++pow;

      System.out.println(testi);

    }

    return (pow-1);

  }


}