Mathematics desk
< July 29	<< Jun \| July \| Aug >>	July 31 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

July 30

Simplify digits population count of n!

Hello,

The aim is to sort the least used digits in ascending order beside 0 :
for example :

87125897! is 7 ; 4 ; 6 ; 9 ; 8 ; 3 ; 5 ; 1 ; 2
87125891! is 1 ; 7 ; 2 ; 6 ; 9 ; 4 ; 8 ; 5 ; 3

What’s the simpler way to get those results without computing the factorial ? 2A01:E0A:401:A7C0:D5E2:84B2:BB18:513F (talk) 08:39, 30 July 2021 (UTC)[reply]

How did you obtain these sorted sequences? Written out in decimal notation, 87125897! has 1,484,003,633 digits, not counting trailing zeroes. Did you really compute these? If not, you apparently already have a shortcut. --Lambiam 19:45, 30 July 2021 (UTC)[reply]

For the examples above, I naïvely computed the factorials and converted them to a text variable in order to count the number of each digit in the number, then sorted the result. But I think there’s more efficient. Took me about 1 minute and 30 seconds per examples 2A01:E0A:401:A7C0:A188:3924:A78B:FE13 (talk) 21:13, 30 July 2021 (UTC)[reply]

I see. I'm afraid there is no substantially simpler way than computing the factorial, for which some methods are better than others; see the PrimeSwing and ParallelPrimeSwing algorithms linked to from this page. --Lambiam 22:03, 30 July 2021 (UTC)[reply]

Do you mean “Please dial population count of 125 885 factorial in ascending order” could be very simple and effective solution to https://en.wikipedia.org/wiki/Wikipedia:Reference_desk/Archives/Computing/2021_July_20#Which_simple_challenge_you_can_ask_to_someone_over_the_phone_using_common_math_in_order_to_ask_him_to_prove_he_as_a_specific_computing_power.3F ?

As I’m using ɢᴍᴘ, I’m confident in the factorial method being used, but how to count the number of times a digit occurs in a number without converting that number to text ? 2A01:E0A:401:A7C0:A188:3924:A78B:FE13 (talk) 22:56, 30 July 2021 (UTC)[reply]

If I was the challenged party, I would not understand the meaning of "dial population count", and it would take me at least two minutes to install GMP on my computer. The algorithm for converting a number to its representation in base 10 consists essentially of repeating integral division by 10 while taking note of the remainder, which is a value in the range 0 to 9. This produces the digits in the reverse order of the left-to-right order in which the decimal representation is written. If only the occurrence count of the digits is needed, there is no need to store them in a long string; all that is needed is to keep count of each type as they are produced. --Lambiam 08:24, 31 July 2021 (UTC)[reply]

When asked “Population count” about a number it involves a well known statistical operation about random number generation in my field. Having a computer with hundreds gigabytes of spare ʀᴀᴍ unusued and a ɢᴍᴘ enabled command prompt installed is also common.

I have doubts about what you are saying because ɢᴍᴘ takes almost as long as doing a dozen of separate Integral divisions than converting the whole number to a string. 2A01:E0A:401:A7C0:A188:3924:A78B:FE13 (talk) 13:32, 31 July 2021 (UTC)[reply]

You never told us the challenged party was cognizant of the jargon of some field involving random number generation and could be expected to have related tools. If you have random access to the bytes of the binary representation, the conversion can be done by consuming the bit string left-to-right, using 6 decimal-string additions per 1.25 bytes in which some loops can be merged. So I suppose GMP has a similar highly specialized and heavily optimized algorithm. The decimal digits of the final result will only emerge in the last round. --Lambiam 17:52, 31 July 2021 (UTC)[reply]

About the fast methods to compute a factorial : things like PrimeSwing are for computing factorials through approximations, but since in my case, the factorial is needed almost in full, (and thus ɢᴍᴘ is more efficient than ᴍᴘꜰʀ) isn’t there a better algorithm working in parallel over 16 threads or even better, capable of being using ꜱɪᴍᴅ for things like ɢᴘᴜ and avx512 ? 2A01:E0A:401:A7C0:F862:E147:4573:55EC (talk) 13:16, 4 August 2021 (UTC).[reply]

I think PrimeSwing computes the exact factorial as a bigint. --Lambiam 20:17, 4 August 2021 (UTC)[reply]

No I looked and it is an approximation algorithm. 2A01:E0A:401:A7C0:486A:484A:4E1D:9B81 (talk) 15:09, 5 August 2021 (UTC)[reply]

Have you profiled your current solution where you use GMP to calculate the exact factorial, convert to a decimal representation in a character string, and then then sort the string? Does the conversion to a string take a significant amount of time compared to the factorial itself? What about the sorting step you mentioned? You don't need to do a sort to get the digit frequencies. But again, if the factorial is the bottleneck, it won't help much to optimize the other steps. If it does turn out to be worthwhile to optimize the steps after the factorial, binary-coded decimal might be a better choice than a character string, and you should consider a frequency count that doesn't involve a full sort. --Amble (talk) 17:05, 4 August 2021 (UTC)[reply]

I suggest that this problem is not a good solution to your "over the phone challenge" problem. It takes 19 bits to store one population count, so you could precompute and store all the results up to one billion factorial in a lookup table of about 2.4 GB. Ideally, your challenge should be chosen such that it would not be feasible to make a lookup table. On that basis, I'd say that requesting the kth digit of n! might be a better choice. --Amble (talk) 17:27, 4 August 2021 (UTC)[reply]

But the problem is the people making the calls does have to know the challenge type before in order to know what to precompute.

Yes, I did profiling, converting to decimal takes 10 or 14 times longer than computing the factorial itself. 2A01:E0A:401:A7C0:486A:484A:4E1D:9B81 (talk) 15:09, 5 August 2021 (UTC)[reply]

Sure, although that's security through obscurity. A better approach would be to use a problem where a lookup table wouldn't be feasible even given knowledge of the challenge type.
That's surprising to me, but OK. I assume you're not including the frequency count step (or sort step!) but only talking about the conversion to decimal. It might be possible to speed this up by combining the decimal conversion and frequency count steps so that you never need to store the very large character string. These steps become trivial if you do the entire computation in binary-coded decimal (although you might have to write your own optimized libraries for this). --Amble (talk) 17:03, 5 August 2021 (UTC)[reply]

finding huge highly composite numbers

How might one go about finding the highly composite numbers that bracket a given huge number?

Motivation: for scifi purpose, I'd like to use a highly composite multiple of the Planck time to approximate one of your Earth days, hence to bracket 1.6026e+48. (Alternatively 2*41! =~ 25h 3m.) —Tamfang (talk) 18:37, 30 July 2021 (UTC)[reply]

If you look how fast the highly composite numbers grow, the bracket around the numerical value of the Planck day will very likely have an enormous span, which may make the feat seem less impressive. I don't know if this helps, but if we agree that the Gödel number of the sequence 4,2,1,1 is 2⁴3²5¹7¹ = 5040, then we can define the Ledög sequence of the number 5040 as the sequence 4,2,1,1. The Ledög sequence of a highly composite number is weakly descending. This constrains the search (but not a whole lot). Here are the Ledög sequences of the first few highly composite numbers, with commas omitted: ; 1; 2; 11; 21; 31; 22; 41; 211; 311; 221; 411; 321; 421; 3111; 2211; 4111; 3211; 4211; 3311; ... --Lambiam 21:01, 30 July 2021 (UTC)[reply]

This sounds like you want p-smooth numbers for small values of p. There are some cute ways to generate those in increasing order: see Regular number#Algorithms, or sample code[1] at Rosetta Code for the 5-smooth aka "Hamming number" case. Many of the approaches there can probably be adapters to larger factor sets. Look at the simplest Haskell example on that page for the basic approach, that you can adapt to your favourite language. Running that algorithm up to numbers like 1e48 is not too bad. 2601:648:8202:350:0:0:0:2B99 (talk) 06:43, 31 July 2021 (UTC)[reply]

The article highly composite number links to a page by Achim Flammenkamp at the University of Bielefeld [2] that includes a table [3] of the first 1200 examples, going up to 5x10⁸⁸. Entry number 532 is 1.268784x10⁴⁸ and 533 is 1.675445x10⁴⁸. --Amble (talk) 20:06, 2 August 2021 (UTC)[reply]

And #738 beats the age of the universe. Keen, thanks! —Tamfang (talk) 00:41, 5 August 2021 (UTC)[reply]