Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given:

ns_num(n, seed, modulo, incrementor) = (seed + n * incrementor) % modulo

n is in range $[0,10000000)$

What value of seed, modulo, and increment can I use such that ns_num yields only values from $62^5$ to $(62^6 - 1)$, and such that no values appear more than once for any given n; where seed, modulo, and incrementor are the same for each call of ns_num.

The point of this function is that I want ns_num to generate a somewhat random sequence of numbers that don't repeat.

My understanding is that modulo and incrementor must be prime to ensure no repeating number.

Is this possible?

share|improve this question
    
What does "Seed" and "increment" mean in programming language? –  JavaMan Jun 7 '11 at 17:53
    
@DJC: Nothing. They are just numbers here. –  ShreevatsaR Jun 7 '11 at 18:02
add comment

2 Answers 2

One choice is seed=$62^5$, incrementor=$1$, modulo$ \ge 62^6-1$. As $62^6-1-62^5 \approx 5.6E10$ and your range of $n$ is $10^7$ (if I have counted the zeros correctly), any incrementor less than $5580$ will work because it won't roll over. Your are right that if incrementor and modulo are relatively prime (have greatest common divisor of $1$) you will not repeat until modulo calls. They do not have to be actual primes-$32$ and $49$ would work. But that doesn't answer the need to return numbers greater than $62^5$. Is it acceptable to use a modulo of $62^6-1-62^5$ (or slightly smaller), generate a value in the range (1,modulo) and add $62^5$ to the output?

share|improve this answer
    
I don't see why not, as long as the output is not sequential when inputs of n are sequential. –  Bradford Jun 7 '11 at 18:17
add comment

I will note that in the question, you noted that you want 'no values to appear more than once for any given n,' but this does not make very much sense as it is a function of n. Thus when you input n, you will get $f(n)$ back, and this will always be the same (unless we change the definition of the function from one trial to the next, which I did not gleam was necessary from your question).

So I assume that you meant instead that no number would be hit by different n, i.e. that the function is "injective."

We'll go at this from a few different perspectives. Firstly, it is easy to satisfy your demand. For example, the function $g(n) = (0 + n*1) \mod{65^6 - (65^5)}$ will yield a number $y$, and then you could always take $x=y + 65^5$ - this will always fall in your range of numbers, and for the first $65^6 - (65^5+1)$ numbers, it will never repeat. This, it turns out, it maximal, as every possible number in the range is hit exactly once. Note that $65^6 - 65^5$ is roughly one thousand times larger than your needed range, so you have a good amount of wiggle room.

There are lots of choices available, and making them prime makes it easier (you are right). But it's not absolutely necessary.

However, you said that you wanted a somewhat random-seeming function. From this, I think that you wanted to be able to plug in different n and get "random" numbers. Of course, it then becomes problematic - how do you choose n? Will you just go through them? If the true goal is seeming randomness, then I don't think that a function of this style will every generate a random sequence. The fact that it's a constant increment is what gives it away. But choosing larger primes would perhaps make it seem more random (as it would loop around more, potentially obscuring the constant increment... temporarily).

Does that make sense?

share|improve this answer
    
It does make sense. First thanks for introducing me to the term injective. To answer your question, n will be provided sequentially. So I will be given n = 1, then n =2, then n = 3, etc... I don't care that someone could figure out the pattern. I just want it to appear somewhat random. Looping around more to "obscure the constant increment" is ideal. I just don't know what values to use for this. –  Bradford Jun 7 '11 at 18:24
    
@Bradford: then you want an increment relatively prime to the modulus 62^6-62^5-1=1373*40702187 so it doesn't repeat. Maybe around 61.8% of that (taken from $\phi -1$) so it bounces around a lot. This gives 34,536,375,501=3*1949*5906683 as a reasonable choice –  Ross Millikan Jun 8 '11 at 2:05
    
@Ross: Thanks Ross! I didn't even realize that he had commented. Thanks for picking up my slack. –  mixedmath Jun 8 '11 at 2:13
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.