Cool Perfect Power Function!!!

krassi_holmz · 2006-05-20 20:57:32

int x is a perfect power iff there exists int a and int b for which

.
For example, 4 and 8 are perfect powers, but 10 isn't.
The function

gives the n-th perfect square.

etc.
The sequence

is very interesting. I'll post some properties of it.

krassi_holmz · 2006-05-20 21:04:13

First, a program. (C++ )

#include<iostream>
#include<fstream>
#include<math.h>
using namespace std;
const long int n=1000000;
int main(){
	//making the array
	cout<<"n = "<<n<<endl;
	bool result[n];
	for(long int i=1;i<n;i++){
		result[i]=false;
	}
	for(long int i=2;i<=sqrt((double)n)+1;i++){
		if(!result[i-1]){
			long int pw=i*i;
			while(pw<=n){
				result[pw-1]=true;
				pw*=i;
			}
		}
	}
	ofstream file("results.txt",ios::out);
	for(long int i=0;i<n;i++){
		if(result[i]){
			file<<i+1<<",";
		}
	}
	cout<<"For results, see 'results.txt'. Press any key to quit:";
	char c;
	cin>>c;
	return c;
}

This is some kind of Erastrotenes prime sieve.
But there's some bug: for n=1000000 (milion) it works fine, but somewhere between 1010000 and 11000000 it starts to give some overflow error.

krassi_holmz · 2006-05-20 21:06:34

Here's S up to i=1000000(milion):

1,4,8,9,16,25,27,32,36,49,64,81,100,121,125,128,144,169,
196,216,225,243,256,289,324,343,361,400,441,484,512,529,
576,625,676,729,784,841,900,961,1000,1024,1089,1156,1225,
1296,1331,1369,1444,1521,1600,1681,1728,1764,1849,1936,
2025,2048,2116,2187,2197,2209,2304,2401,2500,2601,2704,
2744,2809,2916,3025,3125,3136,3249,3364,3375,3481,3600,
3721,3844,3969,4096,4225,4356,4489,4624,4761,4900,4913,
5041,5184,5329,5476,5625,5776,5832,5929,6084,6241,6400,
6561,6724,6859,6889,7056,7225,7396,7569,7744,7776,7921,
8000,8100,8192,8281,8464,8649,8836,9025,9216,9261,9409,
9604,9801,10000,10201,10404,10609,10648,10816,11025,11236,
11449,11664,11881,12100,12167,12321,12544,12769,12996,13225,
13456,13689,13824,13924,14161,14400,14641,14884,15129,15376,
15625,15876,16129,16384,16641,16807,16900,17161,17424,17576,
17689,17956,18225,18496,18769,19044,19321,19600,19683,19881,
20164,20449,20736,21025,21316,21609,21904,21952,22201,22500,
22801,23104,23409,23716,24025,24336,24389,24649,24964,25281,
25600,25921,26244,26569,26896,27000,27225,27556,27889,28224,
28561,28900,29241,29584,29791,29929,30276,30625,30976,31329,
31684,32041,32400,32761,32768,33124,33489,33856,34225,34596,
34969,35344,35721,35937,36100,36481,36864,37249,37636,38025,
38416,38809,39204,39304,39601,40000,40401,40804,41209,41616,
42025,42436,42849,42875,43264,43681,44100,44521,44944,45369,
45796,46225,46656,47089,47524,47961,48400,48841,49284,49729,
50176,50625,50653,51076,51529,51984,52441,52900,53361,53824,
54289,54756,54872,55225,55696,56169,56644,57121,57600,58081,
58564,59049,59319,59536,60025,60516,61009,61504,62001,62500,
63001,63504,64000,64009,64516,65025,65536,66049,66564,67081,
67600,68121,68644,68921,69169,69696,70225,70756,71289,71824,
72361,72900,73441,73984,74088,74529,75076,75625,76176,76729,
77284,77841,78125,78400,78961,79507,79524,80089,80656,81225,
81796,82369,82944,83521,84100,84681,85184,85264,85849,86436,
87025,87616,88209,88804,89401,90000,90601,91125,91204,91809,
92416,93025,93636,94249,94864,95481,96100,96721,97336,97344,
97969,98596,99225,99856,100000,100489,101124,101761,102400,
103041,103684,103823,104329,104976,105625,106276,106929,
107584,108241,108900,109561,110224,110592,110889,111556,
112225,112896,113569,114244,114921,115600,116281,116964,
117649,118336,119025,119716,120409,121104,121801,122500,
123201,123904,124609,125000,125316,126025,126736,127449,
128164,128881,129600,130321,131044,131072,131769,132496,
132651,133225,133956,134689,135424,136161,136900,137641,
138384,139129,139876,140608,140625,141376,142129,142884,
143641,144400,145161,145924,146689,147456,148225,148877,
148996,149769,150544,151321,152100,152881,153664,154449,
155236,156025,156816,157464,157609,158404,159201,160000,
160801,161051,161604,162409,163216,164025,164836,165649,
166375,166464,167281,168100,168921,169744,170569,171396,
172225,173056,173889,174724,175561,175616,176400,177147,
177241,178084,178929,179776,180625,181476,182329,183184,
184041,184900,185193,185761,186624,187489,188356,189225,
190096,190969,191844,192721,193600,194481,195112,195364,
196249,197136,198025,198916,199809,200704,201601,202500,
203401,204304,205209,205379,206116,207025,207936,208849,
209764,210681,211600,212521,213444,214369,215296,216000,
216225,217156,218089,219024,219961,220900,221841,222784,
223729,224676,225625,226576,226981,227529,228484,229441,
230400,231361,232324,233289,234256,235225,236196,237169,
238144,238328,239121,240100,241081,242064,243049,244036,
245025,246016,247009,248004,248832,249001,250000,250047,
251001,252004,253009,254016,255025,256036,257049,258064,
259081,260100,261121,262144,263169,264196,265225,266256,
267289,268324,269361,270400,271441,272484,273529,274576,
274625,275625,276676,277729,278784,279841,279936,280900,
281961,283024,284089,285156,286225,287296,287496,288369,
289444,290521,291600,292681,293764,294849,295936,297025,
298116,299209,300304,300763,301401,302500,303601,304704,
305809,306916,308025,309136,310249,311364,312481,313600,
314432,314721,315844,316969,318096,319225,320356,321489,
322624,323761,324900,326041,327184,328329,328509,329476,
330625,331776,332929,334084,335241,336400,337561,338724,
339889,341056,342225,343000,343396,344569,345744,346921,
348100,349281,350464,351649,352836,354025,355216,356409,
357604,357911,358801,360000,361201,362404,363609,364816,
366025,367236,368449,369664,370881,371293,372100,373248,
373321,374544,375769,376996,378225,379456,380689,381924,
383161,384400,385641,386884,388129,389017,389376,390625,
391876,393129,394384,395641,396900,398161,399424,400689,
401956,403225,404496,405224,405769,407044,408321,409600,
410881,412164,413449,414736,416025,417316,418609,419904,
421201,421875,422500,423801,425104,426409,427716,429025,
430336,431649,432964,434281,435600,436921,438244,438976,
439569,440896,442225,443556,444889,446224,447561,448900,
450241,451584,452929,454276,455625,456533,456976,458329,
459684,461041,462400,463761,465124,466489,467856,469225,
470596,471969,473344,474552,474721,476100,477481,478864,
480249,481636,483025,484416,485809,487204,488601,490000,
491401,492804,493039,494209,495616,497025,498436,499849,
501264,502681,504100,505521,506944,508369,509796,511225,
512000,512656,514089,515524,516961,518400,519841,521284,
522729,524176,524288,525625,527076,528529,529984,531441,
532900,534361,535824,537289,537824,538756,540225,541696,
543169,544644,546121,547600,549081,550564,551368,552049,
553536,555025,556516,558009,559504,561001,562500,564001,
565504,567009,568516,570025,571536,571787,573049,574564,
576081,577600,579121,580644,582169,583696,585225,586756,
588289,589824,591361,592704,592900,594441,595984,597529,
599076,600625,602176,603729,605284,606841,608400,609961,
611524,613089,614125,614656,616225,617796,619369,620944,
622521,624100,625681,627264,628849,630436,632025,633616,
635209,636056,636804,638401,640000,641601,643204,644809,
646416,648025,649636,651249,652864,654481,656100,657721,
658503,659344,660969,662596,664225,665856,667489,669124,
670761,672400,674041,675684,677329,678976,680625,681472,
682276,683929,685584,687241,688900,690561,692224,693889,
695556,697225,698896,700569,702244,703921,704969,705600,
707281,708964,710649,712336,714025,715716,717409,719104,
720801,722500,724201,725904,727609,729000,729316,731025,
732736,734449,736164,737881,739600,741321,743044,744769,
746496,748225,749956,751689,753424,753571,755161,756900,
758641,759375,760384,762129,763876,765625,767376,769129,
770884,772641,774400,776161,777924,778688,779689,781456,
783225,784996,786769,788544,790321,792100,793881,795664,
797449,799236,801025,802816,804357,804609,806404,808201,
810000,811801,813604,815409,817216,819025,820836,822649,
823543,824464,826281,828100,829921,830584,831744,833569,
835396,837225,839056,840889,842724,844561,846400,848241,
850084,851929,853776,855625,857375,857476,859329,861184,
863041,864900,866761,868624,870489,872356,874225,876096,
877969,879844,881721,883600,884736,885481,887364,889249,
891136,893025,894916,896809,898704,900601,902500,904401,
906304,908209,910116,912025,912673,913936,915849,917764,
919681,921600,923521,925444,927369,929296,931225,933156,
935089,937024,938961,940900,941192,942841,944784,946729,
948676,950625,952576,954529,956484,958441,960400,962361,
964324,966289,968256,970225,970299,972196,974169,976144,
978121,980100,982081,984064,986049,988036,990025,992016,
994009,996004,998001,1000000

I'll use this data to make some plots.

Last edited by krassi_holmz (2006-05-20 21:10:48)

krassi_holmz · 2006-05-20 21:12:48

Very interesting.
Look at the plot:

Last edited by krassi_holmz (2006-05-20 21:13:39)

krassi_holmz · 2006-05-20 21:14:37

Here's a plot up to 1000:

Last edited by krassi_holmz (2006-05-20 21:15:21)

krassi_holmz · 2006-05-20 21:15:55

It looks familiar.

krassi_holmz · 2006-05-20 21:28:45

Look:
(sorry but I hurry and can't make better for now)

krassi_holmz · 2006-05-20 21:35:09

Now some pure maths:
1. (it is simple):

.
2. find the nmber of all perfect powers less or equal to x.
3. What can you say about the increasing of P?
I think it diverges.(the increasing, not the function, although F diverges too).

Last edited by krassi_holmz (2006-05-20 21:36:17)

krassi_holmz · 2006-05-20 21:52:05

Let

means
, where p_i is the n=th prime.

krassi_holmz · 2006-05-20 22:05:03

Now, if

is a perfect power, then there exists prime p such:
(1).
p divides i with probability 1/p, so the probability that (1) is tue, is 1/p^n.
So the probability x to be a perfect power is:
, where P is the set of prime numbers.
But now, every i may be every number between 0 and infty and the resulting x will be always different, so if is the set of all numbers that are divisible only by , then exactly of them will be perfect powers.
Now, when n goes to infty, we get that the distribution of the perfect powers is in the set of the integers is:
.
Now that's a hard sum!!!
(it will be < 1, because )

Last edited by krassi_holmz (2006-05-20 22:16:25)

krassi_holmz · 2006-05-20 22:23:16

Now, how to find

???
Any ideas?
(and you can disscuss my work and report for errors)

mikau · 2006-05-21 03:16:56

I see I'm not the only one who has conversations with himself.

I like this function, and the graph is cool. Looks like a nice parabolla to me. However I believe this function is not continuous or differentiable. Still I like nifty functions like this.

luca-deltodesco · 2006-05-21 03:52:55

mikau wrote:

I see I'm not the only one who has conversations with himself.

i only usually do when im figuring something out and asking at the same time, and then end up answering myself before anyone responds

Ricky · 2006-05-21 03:59:51

However I believe this function is not continuous or differentiable.

No function defined on the integers (or naturals as is this case) can be continuous or differentiable. For any function to be continuous at any given point, that point must be a limit point. In functions of integers, there are no limit points.

Edit:

Actually, it's a bit more complicated than that. For example, the function:

f(n) = 1/n for all n in N

Is continous at 0 (when n goes to infinity). But the function krassi is talking about has no limit points.

Very cool function krassi.

mikau · 2006-05-21 05:32:50

No function defined on the integers (or naturals as is this case) can be continuous or differentiable.

Right, I know that, I just wasn't sure if krassi had developed a formula for the intermediate points.

Mathaphobe · 2006-05-21 06:20:26

-To tell the truth i think we all talk to our selves.. (after 3 or 4 Dr. Peppers i know i do...)

-As for the grapic thingy that is way beyond my abiliy so It looks cool...
-Though i'd just use a graphic calculator there are no errors in those at least i hope not...

John E. Franklin · 2006-05-22 12:12:46

kras, why no 'L' in this line?: const long int n=1000000L;

Ricky · 2006-05-22 13:26:15

In most compilers, long is the same as int, 32 bits. So it wouldn't matter. Long is (right now) an artifact of when you had 16 bit ints and 32 bit longs. But now ints are 32 bits, and having a 64 bit int would make a heck of a lot of more work for the processor, it's really not needed. Although compilers normally also have 64 bit ints like microsoft's INT_64.

But even if it did, ints are 32 bits. That can hold up to 2,147,483,648 values when signed. Thus, 1,000,000 can be stored in 32 bits, so there is no worry anyways.

Now what is going on there is an implicit conversion. The compiler sees that line, and rewrites it as:

const long int n = (const long int)1000000;

You don't have to do the conversion as the compiler will do it for you. Many programmers see this as bad practice though. I think that as long as you know what's going on, it's fine to do.

George,Y · 2006-05-22 23:15:14

Since p is a prime number, how can it divide i?

Last edited by George,Y (2006-05-22 23:15:48)

krassi_holmz · 2006-05-23 00:51:48

Ricky wrote:

In most compilers, long is the same as int, 32 bits. So it wouldn't matter. Long is (right now) an artifact of when you had 16 bit ints and 32 bit longs. But now ints are 32 bits, and having a 64 bit int would make a heck of a lot of more work for the processor, it's really not needed. Although compilers normally also have 64 bit ints like microsoft's INT_64.
But even if it did, ints are 32 bits. That can hold up to 2,147,483,648 values when signed. Thus, 1,000,000 can be stored in 32 bits, so there is no worry anyways.
Now what is going on there is an implicit conversion. The compiler sees that line, and rewrites it as:
const long int n = (const long int)1000000;
You don't have to do the conversion as the compiler will do it for you. Many programmers see this as bad practice though. I think that as long as you know what's going on, it's fine to do.

ok. 32bit integers.
but why i get error when n is 2 millions
please.

krassi_holmz · 2006-05-23 01:01:05

3 is a prime.
3 divides 6 for example

John E. Franklin · 2006-05-23 02:39:53

kras, the biggest number I got to work for n is:
const long int nq=1028428L; //1000000;
The next integer larger creates a beep on running.
I changed the single letter variables to two letter variables just in case there was a conflict.

krassi_holmz · 2006-05-23 02:49:25

Yes. But why?

John E. Franklin · 2006-05-23 03:20:41

kras, I recompiled with a different C compiler, and now it Kraps out on this number:
//lower 1035585
const long int nq=1035584L; //1000000;
//higher 1035584

And by the way, the highest power number I found was 1034289 and a nice mirror image one is 1030301.

Last edited by John E. Franklin (2006-05-23 03:21:31)

John E. Franklin · 2006-05-23 03:22:33

We have to do something about this foul word changer.
It won't even allow C-r-a-pped out, which means stopped working.

Math Is Fun Forum

#1 2006-05-20 20:57:32

Cool Perfect Power Function!!!

#2 2006-05-20 21:04:13

Re: Cool Perfect Power Function!!!

#3 2006-05-20 21:06:34

Re: Cool Perfect Power Function!!!

#4 2006-05-20 21:12:48

Re: Cool Perfect Power Function!!!

#5 2006-05-20 21:14:37

Re: Cool Perfect Power Function!!!

#6 2006-05-20 21:15:55

Re: Cool Perfect Power Function!!!

#7 2006-05-20 21:28:45

Re: Cool Perfect Power Function!!!

#8 2006-05-20 21:35:09

Re: Cool Perfect Power Function!!!

#9 2006-05-20 21:52:05

Re: Cool Perfect Power Function!!!

#10 2006-05-20 22:05:03

Re: Cool Perfect Power Function!!!

#11 2006-05-20 22:23:16

Re: Cool Perfect Power Function!!!

#12 2006-05-21 03:16:56

Re: Cool Perfect Power Function!!!

#13 2006-05-21 03:52:55

Re: Cool Perfect Power Function!!!

#14 2006-05-21 03:59:51

Re: Cool Perfect Power Function!!!

#15 2006-05-21 05:32:50

Re: Cool Perfect Power Function!!!

#16 2006-05-21 06:20:26

Re: Cool Perfect Power Function!!!

#17 2006-05-22 12:12:46

Re: Cool Perfect Power Function!!!

#18 2006-05-22 13:26:15

Re: Cool Perfect Power Function!!!

#19 2006-05-22 23:15:14

Re: Cool Perfect Power Function!!!

#20 2006-05-23 00:51:48

Re: Cool Perfect Power Function!!!

#21 2006-05-23 01:01:05

Re: Cool Perfect Power Function!!!

#22 2006-05-23 02:39:53

Re: Cool Perfect Power Function!!!

#23 2006-05-23 02:49:25

Re: Cool Perfect Power Function!!!

#24 2006-05-23 03:20:41

Re: Cool Perfect Power Function!!!

#25 2006-05-23 03:22:33

Re: Cool Perfect Power Function!!!

Board footer