Smith numbers: Difference between revisions
(→{{header|zkl}}: Added code) |
(→{{header|zkl}}: opps) |
||
Line 73: | Line 73: | ||
}) |
}) |
||
}</lang> |
}</lang> |
||
<lang zkl>smithNumbers |
<lang zkl>sns:=smithNumbers(); |
||
sns.toString(*).println(" ",sns.len()," numbers");</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
Revision as of 06:11, 9 April 2016
Smith numbers are numbers that the sum of the integers that make up that number is the same as the sum of its prime factors excluding 1. The primes are also excluded as they, naturally, satisfy this condition!
Example: 166 => 2 x 83 => 2 + 8 + 3 = 1 + 6 + 6 = 13.
The task: write a program to find all Smith numbers below 10000.
C++
<lang cpp>
- include <iostream>
- include <vector>
- include <iomanip>
void primeFactors( unsigned n, std::vector<unsigned>& r ) {
int f = 2; if( n == 1 ) r.push_back( 1 ); else { while( true ) { if( !( n % f ) ) { r.push_back( f ); n /= f; if( n == 1 ) return; } else f++; } }
} unsigned sumDigits( unsigned n ) {
unsigned sum = 0, m; while( n ) { m = n % 10; sum += m; n -= m; n /= 10; } return sum;
} unsigned sumDigits( std::vector<unsigned>& v ) {
unsigned sum = 0; for( std::vector<unsigned>::iterator i = v.begin(); i != v.end(); i++ ) { sum += sumDigits( *i ); } return sum;
} void listAllSmithNumbers( unsigned n ) {
std::vector<unsigned> pf; for( unsigned i = 4; i < n; i++ ) { primeFactors( i, pf ); if( pf.size() < 2 ) continue; if( sumDigits( i ) == sumDigits( pf ) ) std::cout << std::setw( 4 ) << i << " "; pf.clear(); } std::cout << "\n\n";
} int main( int argc, char* argv[] ) {
listAllSmithNumbers( 10000 ); return 0;
} </lang>
- Output:
4 22 27 58 85 94 121 166 202 265 274 319 346 355 378 382 391 438 454 483 517 526 535 562 576 627 634 636 645 663 666 690 ... 9301 9330 9346 9355 9382 9386 9387 9396 9427 9483 9535 9571 9598 9633 9634 9639 9648 9657 9684 9708 9717 9735 9742 9760 9778 9843 9849 9861 9880 9895 9975 9985
zkl
Uses the code (primeFactors) from Prime decomposition#zkl. <lang zkl>fcn smithNumbers(N=0d10_000,base=10){ // -->(Smith numbers to N)
[2..N].filter('wrap(n){ (pfs:=primeFactors(n)).len()>1 and n.split(base).sum(0)== primeFactors(n).apply("split",base).flatten().sum(0) })
}</lang> <lang zkl>sns:=smithNumbers(); sns.toString(*).println(" ",sns.len()," numbers");</lang>
- Output:
L(4,22,27,58,85,94,121,166,202,265,274,319,346,355,378,382,391, ... 3091,3138,3168,3174,3226,3246,3258,3294,3345,3366,3390,3442,3505, ... 9942,9968,9975,9985) 376 numbers