Need help creating a program that outputs a 6 digit number that fits specific criteria

[Winston7]

For a homework assignment i am required to output all numbers that meet the following criteria

1. Must be a six digit number
2. All digits unique (none are the same)
3. The sum of the digits must be a prime number
4. The permutation of the left-most digit (n) and the smallest digit (k) must be odd—for example: in 645923, the left-most is 6 and the smallest digit is 2. Note: the permutation of n things taken k at a time is computed via: n!/(n-k)!

I must output all possible numbers and the total amount of numbers and I would just appreciate a starting point because I feel like its not very difficult i just do not know where to start. Thanks

[JLBorges]

See: http://www.cplusplus.com/forum/general/209105/

[dhayden]

1. for (int i=100000; i <= 999)...

You will need a way to extract the digits. I suggest a function to extract digits into a vector:
vector<int>getDigits(int num). Write the function and test it.

2. Once you have getDigits() you can write a function to check whether the digits in a number of unique.

3. The maximum sum of digits is 6*9=54. So you could just figure out the primes less than 54 and check whether the number is equal to one of those. So write a function to determine is a number between 1 and 54 is prime. Then call that function with the sum of the digits.

4. write a function to compute the permutation of n,k. Call it with the left most and minimum digit.

[JLBorges]

> You will need a way to extract the digits. ... check whether the digits in a number of unique.

Simpler to start with unique digits and generate six digit numbers made out of those digits.


> The maximum sum of digits is 6*9=54. ... a function to determine is a number between 1 and 54

Between 15 and 39 (inclusive).

From http://www.cplusplus.com/forum/general/209105/

Spoiler, off the cuff, untested etc. (essentially brute force, but not as brutish as the ones suggested earlier):
http://coliru.stacked-crooked.com/a/fbacec38cbab4c26

[dhayden]

Very cool solution, JLBorges.

I coded it up using a for loop and it's much slower: 796ms vs. 30ms for yours.

Your solution misses misses some numbers like 102974, but that could probably be fixed with some tweaking to the permutations you skip. I get 32760 possible numbers. Hmm. That's suspiciously close to 2¹⁵

One thing I noticed while testing: the minimum digit must be 0 or 1. If it's 2 or more then perm(N,k) will be even because it includes N*(N-1) and one of those must be even.

[JLBorges]

> Your solution misses misses some numbers like 102974

Hmm... Have I understood the problem incorrectly? I interpreted
"The permutation of the left-most digit (n) and the smallest digit (k) must be odd"
to yield 012974 which is not odd (left most digit is one, smallest digit is zero).


> the minimum digit must be 0 or 1.

Why is that so?

Consider 864397 - it is a six digit number (1); all digits are unique (2); the sum of the digits, 37, is a prime number (3); and the permutation of the left-most digit and the smallest digit (364897) is odd (4).

[lastchance]

Consider 864397 ... the permutation of the left-most digit and the smallest digit ... is odd

8P3 = 8 * 7 * 6 and is definitely even.

The last criterion amounts to:
{ minimum = 0
OR
minimum = 1 and leftmost is odd }

I'm not even sure about minimum = 0: it's a very philosophical question how you would choose 0 things out of N. There again, I end up doing it quite a lot when out shopping!

[JLBorges]

Try to understand the distinction between the terms permutation and number of k-permutations of n. It is an important distinction.

In mathematics, the notion of permutation relates to the act of arranging all the members of a set into some sequence or order, or if the set is already ordered, rearranging (reordering) its elements, a process called permuting. https://en.wikipedia.org/wiki/Permutation

For instance, { 3, 6, 4, 8, 9, 7 } is a permutation of { 8, 6, 4, 3, 9, 7 },
and std::next_permutation() generates the next (lexicographic) permutation.

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    const int a[] = { 3, 6, 4, 8, 9, 7 } ; 
    
    std::vector<int> b( std::begin(a), std::end(a) ) ; // make a copy
    
    // the permutation of the left most element with the smallest element
    std::iter_swap( b.begin(), std::min_element( std::begin(b), std::end(b) ) ) ; 
    
    // is b a permutation of a?
    std::cout << std::boolalpha << std::is_permutation( std::begin(a), std::end(a), std::begin(b) ) << '\n' ; // true
}

http://coliru.stacked-crooked.com/a/42c95352fdeb13b7

these k-permutations of n are the different ordered arrangements of a k-element subset of an n-set (sometimes called variations in the older literature.) These objects are also known as partial permutations or as sequences without repetition, terms that avoid confusion with the other, more common, meaning of "permutation". The number of such k-permutations of n is denoted variously by such symbols as ... ⁿP_k... P(n,k)
https://en.wikipedia.org/wiki/Permutation#k-permutations_of_n

[lastchance]

I'm citing the original post:

The permutation of the left-most digit (n) and the smallest digit (k) must be odd ... Note: the permutation of n things taken k at a time is computed via: n!/(n-k)!

P(8,3) = ⁸P₃ = 8!/(8-3)! = 8!/5! = 8 * 7 * 6

It's the number of ways of choosing 3 items from 8 when order of choice matters and it's definitely even!

[dhayden]

I had the same interpretation as lastchance. JLBorges, it looks like your interpretation was to exchage the the left-most digit and the smallest digit.

[lastchance]

Hmm. I don't seem to be getting the same number of passwords as others. I'm getting
23760 passwords. (But I'm afraid my list of primes will differ from @JLBorges.)

#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;

//============================

void getDigits( int n, int digits[6] )
{
   for ( int i = 5; i >= 0; i-- )
   {
      digits[i] = n % 10;
      n /= 10;
   }
}

//============================

bool isPrime( int n )
{
   int maxTest = sqrt( n );
   for ( int test = 2; test <= maxTest; test++ ) 
   {
      if ( n % test == 0 ) return false;
   }
   return ( n > 1 );
}

//============================

bool sumIsPrime( int digits[6] )
{
   int sum = 0;
   for ( int i = 0; i <= 5; i++ ) sum += digits[i];
   return isPrime( sum );
}

//============================

bool isUnique( int digits[6] )
{
   for ( int i = 1; i <= 5; i++ )
   {
      for ( int j = 0; j < i; j++ )
      {
         if ( digits[j] == digits[i] ) return false;
      }
   }
   return true;
}

//============================

bool criterion4( int digits[6] )       // shortcut version
{
   int leftmost = digits[0];

   int minval = digits[0];
   for ( int i = 1; i <= 5; i++ )
   {
      if ( digits[i] < minval ) minval = digits[i];
   }
   if ( minval == 0 || ( minval == 1 && ( leftmost % 2 == 1 ) ) ) return true;
   else                                                           return false;
}

//============================

int main()
{
   int digits[6];
   int counter = 0;

   ofstream fout( "passwords" );

   for ( int n = 102345; n <= 987654; n++ )
   {
      getDigits( n, digits );
      if ( isUnique( digits ) && sumIsPrime( digits ) && criterion4( digits ) )
      {
         fout << n << endl;
         counter++;
      }
   }
   cout << "Number: " << counter;
   fout.close();
}

[dhayden]

I had already deleted my code so I had to rewrite it. I was using JLBorges's is_prime() function. When I removed 27 and 39 from the list of primes, my code agrees with lastchances's

[jonnin]

fun fact... if the sum of the digits is divisble by 3, so is the number. 27, summed to 9, is absolutely not prime :)