Find number property and write RPL program (HP-49G,G+, HP 50g)

[Gerson W. Barbosa]

This morning I opened my wallet and found only six bills therein (*). Oddly enough all their serial numbers are odd numbers.

1. Besides being odd numbers, what other property do they share?
2. Write a short RPL program to return a list containing the first n numbers which share that property (the shortest the better). Notice the list shall not contain any number ending in 7 or 5 (except 5 itself).
   

As always, research is allowed and encouraged. Both tasks shouldn't be difficult to accomplish, though.

Have fun!


(*) This is not to be taken seriously, of course. Even if they had only the odd-number property, that would have been quite unlikely.

[Bill Zimmerly]

(09-23-2014 05:41 PM)Gerson W. Barbosa Wrote:  This morning I opened my wallet and found only six bills therein (*). Oddly enough all their serial numbers are odd numbers.

[*]Besides being odd numbers, what other property do they share?

They're all prime numbers.

[Paul Dale]

(09-23-2014 05:41 PM)Gerson W. Barbosa Wrote:  Besides being odd numbers, what other property do they share?

The all have exactly one double digit.

Quote:Write a short RPL program to return a list containing the first n numbers which share that property (the shortest the better). Notice the list shall not contain any number ending in 7 or 5 (except 5 itself).

This doesn't follow from my first observation

Quote:This is not to be taken seriously, of course. Even if they had only the odd-number property, that would have been quite unlikely.

Assuming an even distribution of numbers, the odd number property would be a \( \frac{1}{64} \) chance. Not that unlikely really.



Pauli

[Paul Dale]

(09-23-2014 10:02 PM)Bill Zimmerly Wrote:  They're all prime numbers.

Haven't checked if they are or not, but this wouldn't meet the not ending in 7 criteria in the second part.


- Pauli

[Paul Dale]

(09-23-2014 10:02 PM)Bill Zimmerly Wrote:  They're all prime numbers.

I couldn't help myself and checked, they are all prime!

I'm wondering what property Gerson found now.


- Pauli

[Gerson W. Barbosa]

(09-23-2014 10:02 PM)Bill Zimmerly Wrote:  

(09-23-2014 05:41 PM)Gerson W. Barbosa Wrote:  This morning I opened my wallet and found only six bills therein (*). Oddly enough all their serial numbers are odd numbers.

[*]Besides being odd numbers, what other property do they share?

They're all prime numbers.

Yes, all of them are prime numbers, but this is not the property I am interested in. Notice I said 7 does not belong in the list. So the list in item 2 is a subset of the set of the prime numbers.

Gerson.

P.S.: I forgot to mention 2, an even number, is also on the list. BTW, the size of my RPL program is 88.5 bytes (probably still non-optimal). With argument 3 it will return { 2 3 5 }.

[Gerson W. Barbosa]

(09-23-2014 10:27 PM)Paul Dale Wrote:  

(09-23-2014 05:41 PM)Gerson W. Barbosa Wrote:  This is not to be taken seriously, of course. Even if they had only the odd-number property, that would have been quite unlikely.

Assuming an even distribution of numbers, the odd number property would be a \( \frac{1}{64} \) chance. Not that unlikely really.



Pauli

At first I had written very unlikely, but prior to posting I calculated (1/2)^6 getting 1/64, then I changed it to quite unlikely. Perhaps somewhat unlikely would've been a better option.

Gerson.

[Dieter]

(09-23-2014 05:41 PM)Gerson W. Barbosa Wrote:  This morning I opened my wallet and found only six bills therein (*). Oddly enough all their serial numbers are odd numbers.

Ah, between all those Brazilian Reals there also is a 100 Euro bill, issued by German Bundesbank.

Quote:Besides being odd numbers, what other property do they share?

I do not know if this also applies to Brazilian currency, but the serial number of Euro bills follows a specific pattern. There is an initial letter (here X), followed by a ten-digit number and an 11th check digit. A valid serial number has certain properties, based on its modulo 9 value.

Does this point into the right direction or is it far off ?-)

Dieter

[Gerson W. Barbosa]

(09-24-2014 12:53 PM)Dieter Wrote:  

(09-23-2014 05:41 PM)Gerson W. Barbosa Wrote:  This morning I opened my wallet and found only six bills therein (*). Oddly enough all their serial numbers are odd numbers.

Ah, between all those Brazilian Reals there also is a 100 Euro bill, issued by German Bundesbank.

Hello Dieter,

That one was was bought here at my bank early this year, part of 11 other 100-Euro bills (which were duely spent in Germany, by the way :-)
That particular serial number looked like a prime to me, and I decided to check it, upon which I discovered it was not only a prime number, but a special one. Not so special as a Mersenne primes, but special just the same -- and important in cryptography. As you can see, I didn't use any of my calculators to check for its primality as neither would have give this information ( this is a nice hint :-)

Quote:I do not know if this also applies to Brazilian currency, but the serial number of Euro bills follows a specific pattern. There is an initial letter (here X), followed by a ten-digit number and an 11th check digit. A valid serial number has certain properties, based on its modulo 9 value.

Does this point into the right direction or is it far off ?-)

I wasn't aware of the check digit, this is new to me, thanks! I mentioned somewhere in this trade those numbers are part of a subset of the set of primes, so the property is related itself to prime numbers. I also said the first three elements are { 2 3 5 }. OEIS gives too many sequences starting with these, so it won't help. But I also said 7 didn't belong in the list.
Only 22% of the first thousand prime numbers are in the list, and this percentage drops to about 8% for the first million numbers, so I was amazed at finding one 11-digit such prime in a universe of only 12 numbers.
Too many hints by now :-)

Once the property is found, the RPL program is almost straightforward on the HP-49G/G+ or 50g. I have two programs, one that gives the list of the first n elements and another that gives the list of the elements up to a certain value, sometimes with one element in excess ( 88.5 and 86 bytes, respectively).

Cheers,

Gerson.

P.S.: I traded the Euro bill back to Brazilian Reais yesterday ( I wouldn't keep it forever just because a mathematical property :-) and got 6 R$50 bills, one R$5 bill and one R$1 coin. Only two odd-number serials, none prime...

[Thomas Ritschel]

(09-24-2014 04:04 PM)Gerson W. Barbosa Wrote:  Only 22% of the first thousand prime numbers are in the list, and this percentage drops to about 8% for the first million numbers, so I was amazed at finding one 11-digit such prime in a universe of only 12 numbers.
Too many hints by now :-)

That were indeed too many hints!
Your numbers are Sophie-Germain primes, e.g. prime numbers p for which 2p+1 is also prime.

Unfortunately I don't have my 50g with me right now. So I would leave it to someone else to present a RPL solution...

[Gerson W. Barbosa]

(09-24-2014 05:05 PM)Thomas Ritschel Wrote:  

(09-24-2014 04:04 PM)Gerson W. Barbosa Wrote:  Only 22% of the first thousand prime numbers are in the list, and this percentage drops to about 8% for the first million numbers, so I was amazed at finding one 11-digit such prime in a universe of only 12 numbers.
Too many hints by now :-)

That were indeed too many hints!
Your numbers are Sophie-Germain primes, e.g. prime numbers p for which 2p+1 is also prime.

Yes, congratulations!

Researching, or searching, the internet was allowed, hence no hints should be necessary, I thought. But if useful resources like Wolfram Alpha or OEIS are not used, then the solution becomes very difficult, as the property is not evident. Who would think of doubling the numbers and adding 1 to the result and finally checking the result for prime? :-)

I think Wolfram Alpha is the easier way. Just submit any of the numbers to W|A and check the properties. For instance:

http://www.wolframalpha.com/input/?i=22408349

OEIS might also have been used. 2, 3, 5 are the first three elements. The next one is 11. This hasn't been given, but might have been tried:

http://oeis.org/search?q=2%2C3%2C5%2C11%...&go=Search

This returns too many sequences as well. But the one we are looking for is the second.

Sorry if somehow I've spoiled it. Item 2 is interesting anyway. Also, in order to make the RPL exercise a little bit more interesting, lets introduce item 2.1:

Given a list of Sophie Germain primes, write an RPL program that retuns the corresponding safe prime numbers. For instance:

{ 2 3 5 11 } --> { 5 7 11 23 }

This is very very simple, of course, but trying to get a shortest program as possible might make for a good exercise.

Quote:Unfortunately I don't have my 50g with me right now. So I would leave it to someone else to present a RPL solution...

Debug4 is an option (I think it contains the required ROM), unless you cannot install it on the computer you are at now.

Cheers,

Gerson.

[Mark Hardman]

(09-24-2014 05:05 PM)Thomas Ritschel Wrote:  

(09-24-2014 04:04 PM)Gerson W. Barbosa Wrote:  Only 22% of the first thousand prime numbers are in the list, and this percentage drops to about 8% for the first million numbers, so I was amazed at finding one 11-digit such prime in a universe of only 12 numbers.
Too many hints by now :-)

That were indeed too many hints!
Your numbers are Sophie-Germain primes, e.g. prime numbers p for which 2p+1 is also prime.

Unfortunately I don't have my 50g with me right now. So I would leave it to someone else to present a RPL solution...

A quick image to verify the solution:

[Gerson W. Barbosa]

(09-24-2014 05:58 PM)Mark Hardman Wrote:  A quick image to verify the solution:

Thanks! It's interesting to notice that the same process applied to two results, IIRC, yields primes again. These belong also in another less dense subset of primes.

[Thomas Ritschel]

Okay, here I am with my RPL solution.

Program 'SGPrimes':

Code:

%%HP: T(3)A(R)F(.);
\<< \-> n
  \<< { } 0 2
    WHILE OVER n <
    REPEAT DUP
      IF ISPRIME?
      THEN DUP 2 * 1 +
        IF ISPRIME?
        THEN SWAP 1 + SWAP ROT OVER + UNROT
        END
      END NEXTPRIME
    END DROP2
  \>>
\>>

Usage examples:

Code:


 5 --> { 2 3 5 11 23 }
10 --> { 2 3 5 11 23 29 41 53 83 89 }
20 --> { 2 3 5 11 23 29 41 53 83 89 112 131 173 179 191 233 239 251 281 293 }

[Thomas Ritschel]

Of course, the first "ISPRIME?" isn't really necessary since all the primes are generated by using the "NEXTPRIME" command.

So here is a shorter and therefore faster version:

Code:

%%HP: T(3)A(R)F(.);
\<< \-> n
  \<< { } 0 2
    WHILE OVER n <
    REPEAT DUP 2 * 1 +
      IF ISPRIME?
      THEN SWAP 1 + SWAP ROT OVER + UNROT
      END
      NEXTPRIME
    END DROP2
  \>>
\>>

[Thomas Ritschel]

(09-24-2014 05:54 PM)Gerson W. Barbosa Wrote:  Also, in order to make the RPL exercise a little bit more interesting, lets introduce item 2.1:

Given a list of Sophie Germain primes, write an RPL program that retuns the corresponding safe prime numbers. For instance:

{ 2 3 5 11 } --> { 5 7 11 23 }

This is very very simple, of course, but trying to get a shortest program as possible might make for a good exercise.

How about the following:

Code:

%%HP: T(3)A(R)F(.);
 \<< 2 * -1 -
 \>>

Subtracting "-1" might seem a bit counterintuitive. But using the more obvious "1 +" would instead append "1" to the list.

[Gerson W. Barbosa]

(09-24-2014 07:23 PM)Thomas Ritschel Wrote:  Of course, the first "ISPRIME?" isn't really necessary since all the primes are generated by using the "NEXTPRIME" command.

So here is a shorter and therefore faster version:

Code:

%%HP: T(3)A(R)F(.);
\<< \-> n
  \<< { } 0 2
    WHILE OVER n <
    REPEAT DUP 2 * 1 +
      IF ISPRIME?
      THEN SWAP 1 + SWAP ROT OVER + UNROT
      END
      NEXTPRIME
    END DROP2
  \>>
\>>

ISPRIME? { ... } IFT is less elegant than IF ISPRIME? THEN ... END, but saves you 5 bytes.
Nice there is no ELSE (IFTE) like mine.

[Gerson W. Barbosa]

(09-24-2014 08:01 PM)Thomas Ritschel Wrote:  

(09-24-2014 05:54 PM)Gerson W. Barbosa Wrote:  Also, in order to make the RPL exercise a little bit more interesting, lets introduce item 2.1:

Given a list of Sophie Germain primes, write an RPL program that retuns the corresponding safe prime numbers. For instance:

{ 2 3 5 11 } --> { 5 7 11 23 }

This is very very simple, of course, but trying to get a shortest program as possible might make for a good exercise.

How about the following:

Code:

%%HP: T(3)A(R)F(.);
 \<< 2 * -1 -
 \>>

Subtracting "-1" might seem a bit counterintuitive. But using the more obvious "1 +" would instead append "1" to the list.

Bingo!

[Paul Dale]

(09-24-2014 04:04 PM)Gerson W. Barbosa Wrote:  P.S.: I traded the Euro bill back to Brazilian Reais yesterday ( I wouldn't keep it forever just because a mathematical property :-) and got 6 R$50 bills, one R$5 bill and one R$1 coin. Only two odd-number serials, none prime...

I did wonder about how long you spent finding these bank notes


- Pauli

[Gerson W. Barbosa]

(09-24-2014 09:35 PM)Paul Dale Wrote:  

(09-24-2014 04:04 PM)Gerson W. Barbosa Wrote:  P.S.: I traded the Euro bill back to Brazilian Reais yesterday ( I wouldn't keep it forever just because a mathematical property :-) and got 6 R$50 bills, one R$5 bill and one R$1 coin. Only two odd-number serials, none prime...

I did wonder about how long you spent finding these bank notes


- Pauli

About 5 months. I'd like to gather 7 of them, but I haven't found any in the last two months so I quit. I got tired of checking bills for primes

Gerson.