Scheduled Maintenance: We are aware of an issue with Google, AOL, and Yahoo services as email providers which are blocking new registrations. We are trying to fix the issue and we have several internal and external support tickets in process to resolve the issue. Please see: viewtopic.php?t=158230

 

 

 

mop number in c

Programming languages, Coding, Executables, Package Creation, and Scripting.
Post Reply
Message
Author
cyborg_o
Posts: 28
Joined: 2005-11-05 16:18

mop number in c

#1 Post by cyborg_o »

i have to write a program calculating an integer's mop number. does anyone know anything about mop numbers?

and my question is what would i do with a mop number?

geoffb
Posts: 122
Joined: 2005-10-19 18:09
Location: Calgary, AB

Re: mop number in c

#2 Post by geoffb »

cyborg_o wrote:i have to write a program calculating an integer's mop number. does anyone know anything about mop numbers?

and my question is what would i do with a mop number?
I've never heard of a mop number.

What level of programming are you at, to give us an idea?

cyborg_o
Posts: 28
Joined: 2005-11-05 16:18

#3 Post by cyborg_o »

i'm at childs play leve - intro to c.

a mop number i'm told by my professor is the lowest representation of a number in terms of 1's.

for example

the mop number of 6 is 5
because 2 times 3 = six or
(1+1) * (1+1+1) = 6
and it has to be the lowest possible one, so

(1+1+1+1+1+1) = 6 is not the mop number

maybe there is another name

for 1 through 5 the mop number is it's self.

for a prime you subtract 1 and find the mop of that number and add 1. for example
7 = 1 + (1+1)*(1+1+1) = 6

the mop number of any number bigger than 5 is less than the number.

that's all i have.

i've got some ideas, but i'm having a hard time with the larger numbers, like 100 and 1000 plus.

thanks

Jeroen
Debian Developer, Site Admin
Debian Developer, Site Admin
Posts: 483
Joined: 2004-04-06 18:19
Location: Utrecht, NL
Contact:

#4 Post by Jeroen »

This is more like math than programming, though it's an interesting task to program an algorithm for. I think you'll need to think of this as puzzle, not as something that will yield you any really useful result.

Jeroen
Debian Developer, Site Admin
Debian Developer, Site Admin
Posts: 483
Joined: 2004-04-06 18:19
Location: Utrecht, NL
Contact:

#5 Post by Jeroen »

Assuming you only use + and *, and no other operators (like power series), you can do this with dynamic programming in O(n^2) time, at least, but if you think about it, you could probably make it go even faster. Mathematically, my intuation says the mop number should be somewhat logarithmic.

Since I'm much more familiar with java, here a quick java solution:

Code: Select all

public class mop
{
  public static void main(String[] args)
  {
    System.out.println(mop(Integer.parseInt(args[0])));
  }

  public static int mop(int n)
  {
    int[] mops = new int[n+1];
    mops[1] = 1;
    for (int i=2;i<=n;i++) {
      mops[i] = i;
      for (int j=1;j<i;j++) {
        if (mops[j] + mops[i-j] < mops[i])
          mops[i] = mops[j] + mops[i-j];
        if (i%j==0 && mops[j] + mops[i/j] < mops[i])
          mops[i] = mops[j] + mops[i/j];
      }
    }
    return mops[n];
  }
}
Oh, and the mop of 100 is 14, that of 1000 is 21. Indeed it shows that all powers of two (except the number 1) hold to: mop(2^n) == 2*n. So write out the first few dozen or so mop number's binary representation, and you'll probably see a system emerge.

cyborg_o
Posts: 28
Joined: 2005-11-05 16:18

#6 Post by cyborg_o »

lol. that's impressive. I've been trying to get something working for days. I have a hard time reading code though. I'm actually an electrical engineer in college. But what's funny is my other major is pure math. I'm humbled.

You used Big O notation right? I've read the Wiki on it. But I would like to know more. I'm very interested in how long calculations take. I think that's very valuable information. Do you know any other online sources to read more about it?

In regards to the program are there any good online sites for beginers to learn data structures and algorithms? Are these subjects somewhat independent of the languaged used?

thank you

Jeroen
Debian Developer, Site Admin
Debian Developer, Site Admin
Posts: 483
Joined: 2004-04-06 18:19
Location: Utrecht, NL
Contact:

#7 Post by Jeroen »

They are very independent of the programming language used. All commonplace programming languages have arrays, variables, integers, float-ing point numbers, functions, etc. Just the syntax tends to differ a bit. C/C++ and Java particularly are extremely similar. As far as algorithms go, you don't need must if anything of the more advanced features of any language.

The most comprehensive book is "The Art of Computer Programming" by Donald Knuth, but there are plenty of more accessible books, just search any book website for 'data structures and algorithms", one good book is "Data Structures and Algorithms in Java" by Goodrich and Tamassia.

cyborg_o
Posts: 28
Joined: 2005-11-05 16:18

#8 Post by cyborg_o »

awesome.

i got the program running today. though i think it is very different from yours. your's is much tinier. later i will put it up on the forum. and maybe you or somebody can show me how to optimize it and make it smaller and faster.

thank you.

i've heard of the knuth. on the pure side of math he is brilliant for surreal numbers. i have a friend who swears by the art of computer programming. though i am intimidated by the books. they may be way beyond my abilities at the moment, but someday...

thanks

Post Reply