Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

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

krassi_holmz
Real Member
Registered: 2005-12-02
Posts: 1,908

Cool Perfect Power Function!!!

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.


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

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

krassi_holmz
Real Member
Registered: 2005-12-02
Posts: 1,908

Re: Cool Perfect Power Function!!!

First, a program. (C++ smile)

#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.


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

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

krassi_holmz
Real Member
Registered: 2005-12-02
Posts: 1,908

Re: Cool Perfect Power Function!!!

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)


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

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

krassi_holmz
Real Member
Registered: 2005-12-02
Posts: 1,908

Re: Cool Perfect Power Function!!!

Very interesting.
Look at the plot:

View Image: PP.GIF

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


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

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

krassi_holmz
Real Member
Registered: 2005-12-02
Posts: 1,908

Re: Cool Perfect Power Function!!!

Here's a plot up to 1000:

View Image: pp1000.GIF

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


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

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

krassi_holmz
Real Member
Registered: 2005-12-02
Posts: 1,908

Re: Cool Perfect Power Function!!!

It looks familiar.


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

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

krassi_holmz
Real Member
Registered: 2005-12-02
Posts: 1,908

Re: Cool Perfect Power Function!!!

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

View Image: pp10e6+pow.GIF

IPBLE:  Increasing Performance By Lowering Expectations.

Offline

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

krassi_holmz
Real Member
Registered: 2005-12-02
Posts: 1,908

Re: Cool Perfect Power Function!!!

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)


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

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

krassi_holmz
Real Member
Registered: 2005-12-02
Posts: 1,908

Re: Cool Perfect Power Function!!!

Let


means
, where p_i is the n=th prime.


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

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

krassi_holmz
Real Member
Registered: 2005-12-02
Posts: 1,908

Re: Cool Perfect Power Function!!!

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)


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

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

krassi_holmz
Real Member
Registered: 2005-12-02
Posts: 1,908

Re: Cool Perfect Power Function!!!

Now, how to find


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


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

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

mikau
Member
Registered: 2005-08-22
Posts: 1,504

Re: Cool Perfect Power Function!!!

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.


A logarithm is just a misspelled algorithm.

Offline

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

luca-deltodesco
Member
Registered: 2006-05-05
Posts: 1,470

Re: Cool Perfect Power Function!!!

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


The Beginning Of All Things To End.
The End Of All Things To Come.

Offline

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

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: Cool Perfect Power Function!!!

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.


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

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

mikau
Member
Registered: 2005-08-22
Posts: 1,504

Re: Cool Perfect Power Function!!!

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.


A logarithm is just a misspelled algorithm.

Offline

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

Mathaphobe
Member
Registered: 2006-05-20
Posts: 18

Re: Cool Perfect Power Function!!!

-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...


Do you like my new avatar? (even if you don't i do smile)
(it's victor from oh my gods)
-An Incremental Development

Offline

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

John E. Franklin
Member
Registered: 2005-08-29
Posts: 3,552

Re: Cool Perfect Power Function!!!

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


igloo myrtilles fourmis

Offline

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

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: Cool Perfect Power Function!!!

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.


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

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

George,Y
Member
Registered: 2006-03-12
Posts: 1,306

Re: Cool Perfect Power Function!!!

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

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


X'(y-Xβ)=0

Offline

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

krassi_holmz
Real Member
Registered: 2005-12-02
Posts: 1,908

Re: Cool Perfect Power Function!!!

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.


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

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

krassi_holmz
Real Member
Registered: 2005-12-02
Posts: 1,908

Re: Cool Perfect Power Function!!!

3 is a prime.
3 divides 6 for example


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

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

John E. Franklin
Member
Registered: 2005-08-29
Posts: 3,552

Re: Cool Perfect Power Function!!!

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.


igloo myrtilles fourmis

Offline

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

krassi_holmz
Real Member
Registered: 2005-12-02
Posts: 1,908

Re: Cool Perfect Power Function!!!

Yes. But why?


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

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

John E. Franklin
Member
Registered: 2005-08-29
Posts: 3,552

Re: Cool Perfect Power Function!!!

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)


igloo myrtilles fourmis

Offline

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

John E. Franklin
Member
Registered: 2005-08-29
Posts: 3,552

Re: Cool Perfect Power Function!!!

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


igloo myrtilles fourmis

Offline

Board footer

Powered by FluxBB