Aeternus

I assume your alphabet is [math]\{1\}[/math]?

In this case, you can just proceed by induction on the length [math]n[/math] of the string. Take a couple of base cases to make it simple. It makes things much simpler if you first of all reduce it to (111*)* = 111*, since clearly 111* has any string of length 2 or greater, which is the same as (111*)*.

In the case [math]n = 0[/math], then due to the outer most Kleene Star in both cases, the empty word is in both languages.

In case [math]n = 1[/math], then as we have no string in either expression of length less than 2, no amount or concatenation or choice will result in a string of length one, so "1" is not in either language.

In case [math]n = 2[/math], then this is clearly in both languages from the definitions of Kleene star and +.

In case [math]n = 3[/math], then this is clearly in both languages from the definitions of Kleene star and +.

Assume for the induction hypothesis that we have the string [math]S[/math] of size [math]n[/math] in the language of both, and the string S' of size [math]n+1[/math] also in the language, and [math]n \ge 3[/math], then consider what happens if we have the string S'' of length [math]n+2[/math].

Clearly S'' is in the language 111* (as this matches any string of length 2 or greater). In case [math]n+2[/math] is odd, then we have that S of length [math]n[/math] is in the language (11 + 111)* and by the definition of the Kleene star S11 is also in the language, and the same argument holds if [math]n+2[/math] is even.

Basically, from 11 and 111, you can make any odd or even sized string of 1s of length greater than 2 by simply adding 11 to either repeatedly (to make all the even or odd sizes.

Why not look at things such as - http://en.wikipedia.org/wiki/Adder_(electronics) ? A nice simple example of computation being done with logic gates.

Well, you sort of half understood and half misunderstood, but before I get into that, let me thank you for your thorough answer. It's much appreciated.

 

Yes, while the factorial has that growth of digits, don't forget we're talking about the primorial, which, if I understood correctly, grows according to

 

[math]exp([1 + o(1)] n \log(n))[/math]

 

Unfortunately, while I have a very vague idea of what o() is regarding functions (it's basically supposed to mean that one function grows much faster than the other, or that the limit of the two functions as they approach infinity is 0), I have no idea what o(1) means...which means I don't know what 1 + o(1) is So, I don't know if it's more or less, however logically it must be less than the factorial. As for comparing it with the Sieve of Atkin, I have absolutely no idea whether or not [math]exp([1 + o(1)] n \log(n))[/math] is bigger than whatever the Sieve of Atking uses. However, don't forget we only have to remember one single number, not a series. Just one huge number, and that's where I hope the strength of this algorithm (if there is any) lies.

 

As for the time to calculate the Primorial, this is where you get me wrong. I don't intend this to be a method to prove primality, I intend it to be a way of generating primes. And since you generate the primorial on the run, you don't have to worry about time. Let me explain this on an example:

 

 

Let us declare a variable [math]p[/math] that will hold the primorial, and a variable [math]x[/math] that will be the current numbers tested.

 

You start out with two (let's just hard code it to make things simpler). So now we have [math]p = 2[/math] and [math]x = 3[/math]. [math]GCD(2, 3) = 1[/math] which means x is a prime. We update the primorial, that is [math] p = px = 6[/math]. And we move on.

 

[math]x = 4, GCD(4, 6) = 2[/math] x is NOT prime.

[math]x = 5, GCD(5, 6) = 1[/math] x is prime, [math] p = px = 30[/math].

[math]x = 6, GCD(30, 6) = 6[/math] x is NOT prime.

[math]x = 7, GCD(30, 7) = 1[/math] x is prime, [math] p = px = 210[/math].

 

And on and on and on.

 

I don't know if this changes anything, but at least you now have a fuller understanding of what I mean (I hope ).

 

Cheers,

 

Gabe

Note here that [math]n\sharp[/math] is not the same as [math]P_n\sharp[/math] and I imagine you should be considering [math]n\sharp[/math] if you are looking at all the primes up to [math]n[/math], which will be much better for you. However, even with this improvement, this still gives a space complexity of [math]O(n)[/math] (from the wiki), which is still worse than Sieve of Atkins.

Note here, that whatever your space complexity, your time complexity must be at least that (since you need to write to that many memory locations). You still need to worry about time, since the time to calculate just the final primorial (i.e over the course of the entire algorithm) is too big.

Even if your algorithm wasn't already worse time and space complexity (baring in mind, this is just from calculating that one number, I'm not assuming anything other than the calculation of one primorial), there is also the fact that you still need to calculate the GCD for these huge numbers, which in of itself has quite a bad time complexity from what I know, see http://en.wikipedia.org/wiki/Euclidean_algorithm#Running_time . I imagine there are faster algorithms but from what I gather they are not much faster, and they would have to be at least O(log(n)) (afaik) as you'll need to read the numbers (assuming we are considering [math]n[/math] as the number and not the size of the number - this is something one should be careful of, as various resources approach this differently, and considering it in the size of the number throughout would probably be more appropriate).

If you are genuinely serious about trying to understand this, then I'd honestly suggest you read up on Big O etc, and work through things, rather than hand waving with "one huge number has to be better than lots of smaller numbers", which just doesn't seem to be true. If I've made some mistakes, please point them out.

If you look at http://en.wikipedia.org/wiki/Factorial#Rate_of_growth , you'll see that for bigger [math]n[/math], [math]n![/math] has at least [math]n (\log(n) -1)[/math] digits, which means that for a prime with thousands of digits, you are talking of not thousands of digits but of the order of [math]n\log(n)[/math] digits where [math]n[/math] is thousands of digits itself.

I.e, you are talking at least [math]O(n \log(n))[/math] space complexity as far as I can see, which is worse than that for Sieve of Atkin given at http://en.wikipedia.org/wiki/Sieve_of_Atkin#Computational_complexity , i.e [math]O(n^{\frac{1}{2} + O(1)})[/math] (presumably the constant in the exponent is very small, as it is supposedly better than the Sieve of Eratothenes, although either way, the space complexity can't be worse than the time complexity) although I don't know the constants involved (See http://en.wikipedia.org/wiki/Big_O_notation for a better idea of O notation. If you make another thread of anything you don't understand, people can explain ).

Also, you have to look at the time it takes to calculate a factorial, remembering that multiplication is not a constant time operation. If you look at http://en.wikipedia.org/wiki/Factorial#Computation you'll see that to calculate [math]n![/math] is far worse time complexity than that used for Sieve of Atkins (See http://en.wikipedia.org/wiki/Sieve_of_Atkin#Computational_complexity again).

If you look at the time and space complexities for Sieve of Eratothenes (one of the most well known and oldest algorithms for calculating all prime numbers up to a number), I believe your algorithm would still be worse.

I'm not sure here whether you are suggesting calculating factorials or primorials for each prime test and going through them, but again this is far worse than simply using the sieves or just going through the list of numbers with individual primality tests. If your algorithm only tests whether a single number is prime, and does not find all prime numbers less than that number, then there are MUCH faster algorithms for testing individual primality without calculating all primes - See http://en.wikipedia.org/wiki/Primality_test#Fast_deterministic_tests .

I might be misunderstanding what you are suggesting. If so, could you please explain what I'm misunderstanding.

Well consider that given a number n, you need [math]\log_2(n)[/math] bits to display it, so you have

[math]

N = \log_2(n) [/math]

[math]2^N = 2^{\log_2(n)} [/math]

[math] 2^N = n

[/math]

So you are left with [math]O(2^n)[/math].

Two points to note :

a) Big O and Big Theta are two different things. Big O is only an upper bound, whereas Big Theta is much tighter and must be also a lower bound. See http://en.wikipedia.org/wiki/Big_O_notation#The_family_of_Bachmann-Landau_notations .

b) You only need to check for factors up to [math]\sqrt{n}[/math] rather than [math]\frac{n}{2}[/math]. Consider a number bigger than the square root, then you'd need to multiply it by a number smaller than the square root to get n, otherwise you'd get a number larger than n.

If this is indeed a mathematical problem and not some weird "haha" problem, here's how I'd start it, at least:

 

We have 3 children we don't know their ages, but we do know that they add up to 13:

 

x + y + z =13

 

We have another number on the door (let's call it R) that *we* don't know, but the student does know, so he has another equation:

 

xyz=R

 

What you're missing is another equation (3 variables, 3 equations), and the value of R. It seems to me that the statement about the violin is your clue, and it might be a cultural answer (do people start studying the violin at a certain age in your country, or perhaps it *means* another thing, like the fact he studies the violin means he is a twin, or something?). If you figure that out, you can solve it.

 

I suggest you ask your professor to give you a hint.

[hide]

Or the fact that there is an eldest child, (potentially) implying there aren't 2 eldest children if you only consider integer ages.

[/hide]

Well, what price range are you in? Macs are more expensive, but they work better(mainly because they have better parts and the software is designed for the parts instead of being designed to work on almost anything). Now, you can even use Windows on a Mac bot(and it works better due to better standard parts). About games, many games are made for Macs as well. In fact, I got Fable when I bought my MacBook Pro. However, they are a lot more expensive.

Given personal experience, experiences of friends and also looking around online, I'd say that, while macs USED to be higher quality than your average PC, they are probably about on par these days.

Sounds right. Although you could probably get away with

[math]

(C \setminus A) \cup (B \setminus C)

[/math]

since [math]C \setminus A[/math] will contain the bits that you need from C.

I think you have the wrong idea. From what I gather, when one talks of 10 dimensions, one is not talking about different universes or anything like that (you might be thinking of http://en.wikipedia.org/wiki/Many_worlds but that suggests many more than 10 "universes") but is talking about spacial dimension, in the same way that you have 3 dimensions (i.e height, width and breadth).

The idea being that you don't have just 3 spacial dimensions but in fact 10 spacial dimensions (this is very difficult to imagine, hence the video and various other resources trying to provide a way to imagine it). From what I remember, the ideas that suggest a greater number of spacial dimensions usually say that the dimensions other than the 3 we normally consider are very small and unnoticable, but that sort of thing is probably a massive oversimplification told to the general public on documentaries etc (I'm not a physicist).

The nice thing is that it's not limited to SQL backed systems, you can use LINQ to run through various datastructures that you are using or implement a few interfaces and have your own datastructure usable (through IQueryable etc I believe).

Saying that, the underlying idea isn't completely original, as bascule mentioned previously, things like ActiveRecord and ADO.NET have done similar things (not specifically the query part, but bringing the handling of the data and types into the programming language) but it'll be interesting to use.

Personally I'm more interested in them bringing various features that they require for LINQ, such as lambda expressions, and more functional concepts (which LINQ seems to be part of) and so on, to languages such as VB.NET. There are many times when you just want to do something in a functional manner because it is the quickest and most readable way to do something, and a nice fusion of imperative and functional ideas in languages certainly benefits developers.

You know you can preview your post right ?

answer hidden below

 

[hide]90 mph

 

it's pretty simple. The way there is 30mph and average velocity is 60 mph.

Ave Velocity = (V1 + v2) / 2

 

plug in and solve for V2 [/hide]

I don't think that's correct, you are averaging over distance, not time.

I believe you can't do it.

Take the speed we travel back with to be [math]x[/math].

We have [math] \textrm{average speed} = \frac{\textrm{total distance}}{\textrm{total time}} [/math].

We have the total distance as 60, and the time is going to be the 1 hour we have already used, added to the time it will take us to cover the remaining 30 miles, so [math]\frac{30}{x}[/math].

This gives us

[math] 60 = \frac{60}{1 + \frac{30}{x}} [/math]

[math]1 + \frac{30}{x} = 1 [/math]

[math]\frac{30}{x} = 0 [/math]

As you can see, there is no solution.

If you could travel for another hour at 90 mph, then it would be fine, but you only have 30 miles left to cover.

This is pretty easy.

 

Is 2+3*4 = 24 or 20?

 

(2+3)*4 = 20

2+(3*4) = 24

 

It is picked so that there is a convention. So that even when someone fails or forgets to put the ()'s in, there is a definitive answer. I don't think that any one method is intrinsically superior to the other ... I don't think that 20 is a better or worse answer than 24 to the above question -- except that my brain goes with the established convention and so in that respect part of me does prefer the 24.

 

I think that the rules are there to make it as unambiguous as possible.

 

Maybe someone else will know more about the history or rationale behind them, because I don't...

I think you'll find 2 + (3*4) = 14 .

Well, it's fairly inexpensive, so why not buy it, or get it from the local library or something. If you find it hard to read, it might make a reasonable door stop

I presume they're taking the names from particle physics: a tachyon is a hypothetical particle that travels faster than light, and a tardyon is any particle that travels slower than light.

Strangely it seems they are from different roots (one from greek, one from latin)

http://en.wikipedia.org/wiki/Greek_and_Latin_roots_in_English

There are code tags ( [ code ] and [/ code] (without the spaces)) which you might find useful.

Firstly, you either need to specify the namespaces you are using explicitly on use or overall the namespaces you are using within the file. Your compiler may be ignoring this but you should probably realise it is a problem, as it will come up if you move to others.

Secondly, the second version is almost certainly necessary, as otherwise you'll only ever be able to book one class of ticket.

Thirdly, given that you didn't actually specify what your problem was or what you expected this thing to do, I assume your problem was something akin to the problem I encountered while running this code, which was an issue whereby cin leaves a newline character on stdin, and that then gets picked up when you call getline a second time (after a previous cin call) and so you have to tell cin to ignore the character before calling getline.

If that's not the problem you had, perhaps you could elaborate further.

Here is your code, edited and working as far as I can see (given I don't know exactly what you want -

#include <string>
#include <iostream>

using namespace std;

int main()
{
   int c, s[10];
   int i, j;
   string name;




   for (j=0; j<10; j++) {

       cout << "Welcome to Airline Reservations System!\n";
       cout << "Please enter your name: ";

       cin.ignore();
       getline(cin,name);

       cout << "Choose a class: ";
       cin >> c;

       switch(c) {
           case 1:
               cout << "First class" << endl;
               cout << "Seats available are 1,2,3,4,5.\n";
               do {
                   cout << "Pick a seat: ";
                   cin >> s[j];
                   for (i=0; i<j; i++) if (s[j]==s[i]) {
                       cout << "Seat taken. ";
                       break;
                   }
               } while (i!=j);

               if(s[j] <= 5) {

                   cout << "\n";
                   cout << "--------------------------\n";
                   cout << "Name: " << name << endl;
                   cout << "Class: " << "First class" << endl;
                   cout << "Seat no.: " << s << endl;
                   cout << "--------------------------\n";

               } else cout << "Wrong number! No seat for you!\n";
               break;
           case 2:
               cout << "Economic class\n";
               cout << "Seats available are 6,7,8,9,10.\n";
               do {
                   cout << "Pick a seat number: ";
                   cin >> s[j];
                   for (i=0; i<j; i++) if (s[j]==s[i]) {
                       cout << "Seat taken. ";
                       break;
                   }
               } while (i!=j);
               if(s[j] >= 6)
               {
                   cout << "\n";
                   cout << "--------------------------\n";
                   cout << "Name: " << name << endl;
                   cout << "Class: " << "Economic class" << endl;
                   cout << "Seat no.: " << s[j] << endl;
                   cout << "--------------------------\n";
               }
               else cout << "Wrong number! No seat for you!\n";
               break;
       }
   }


   system("pause");
   return 0;
}

You may also want to look into initialising your array (I'm not entirely sure on the C++ standard but in C, uninitialised content could be anything) and you may want to check that cin etc actually return something properly (remember I can press ctrl+d).

Also, you may want to read Things to Avoid in C/C++ -- system("pause").

I'll probably comment more fully after my exams tomorrow.

Ruined? Most peoples issues with macs tend to be lack of familiarity in my experience... Mine tends to be the mice, keyboards and lack of virtual desktops though, but that's mostly because of uni ones, and none of that would matter for a new user.

I believe they have spaces in Leopard. Although I'd prefer a decent linux distribution over OS X these days, it's just easier to use most OSS tools and utilities, and I'd rather not support yet another proprietary OS and environment (bit hypacritical as I'm typing this on a macbook but my next laptop won't be a mac).

If you don't mind it being symmetric about the y axis and only want strong growth not assymptotic like Capn's, then you might also consider something similar to what Bignose suggested -

[math]

y = e^{(\frac{x}{a})^b} - 1

[/math]

Where you can change [math]a[/math] to change where it begins growing very quickly and change [math]b[/math] to change how quickly it grows at that point and how gradually it grows before that.

To generalise what Capn said a bit, if you want assymptotic behaviour, similar to what he said you can do

[math]

y = \frac{1}{b \cdot x-b \cdot a}

[/math]

Where [math]a[/math] and [math]b[/math] have similar effects as above.

[math]x^2[/math] is not an exponential function or even a function exhibiting exponential growth.

See http://en.wikipedia.org/wiki/Exponential_growth .

I imagine the answer to your question is really going to depend on what exactly you want and what you mean by "in the beginning" and gradual growth. Can you go into a bit more detail about what it is you want to derive?

I'd like to point you to

http://en.wikipedia.org/wiki/Rubber_hose_cryptanalysis

One of the most fun and effective methods

If you explain a bit more what you are trying to do, then people can tell you whether your cryptosystem is likely to be any good (this isn't to say that one needs to know what cipher you are using to cryptanalyse it, only that it's much easier to narrow down the field and explain principles without wasting time on a pointless exercise). The fact that you are trying to rely on security through obscurity seems rather ominous of a bad cipher in any case though ( See http://en.wikipedia.org/wiki/Kerckhoffs%27_principle ) .

Shouldn't it be mentioned that the theorem initially mentioned in the first post refers to Gödel's Second Incompleteness Theorem (which uses the first but isn't the same theorem), while later posts refer to the First Incompleteness Theorem.

Also "Gödel's Theorem for Dummies" is a little non-specific as he is known for several other theorems including his Completeness Theorem.

To clarify, wasn't the issue that the people making the crown could have added some silver into the crown so that it would weigh the same as a gold crown but they could pocket the surplus gold.

Therefore Archimedes realised that gold and silver are different densities and so if they weighed the same, the volume would be different but doing this by eyesight, with such a difference, would be rather hard and so the bath trick comes in where he can put a gold bar into some water, and then put the crown in (seperately) and if the water doesn't rise by the same amount, then it's off with the jewellers/goldsmiths head

http://en.wikipedia.org/wiki/Archimedes

I disagree that boycotting is blackmail as far as the strictly defined meaning of the word goes and especially not in the spirit of the word as it is used, but I can certainly see where the argument is coming from.

Personally, however, I've never seen anything wrong with blackmail, except in the situation where the blackmail revolves around some other illegal act (as then blackmail being illegal makes sense as it makes it less likely the act will be hidden, although I imagine withholding evidence is illegal anyway?).

As far as I see it, someone does something questionable, you offer them the chance to keep said questionable act secret by offering some benefit to you. If they say no, then you do what you would have otherwise done and make that questionable act public. Making the questionable act public is not illegal, keeping it a secret without an offer is not illegal, so I do not understand why adding some condition into the mix all of a sudden makes it illegal, although I suppose one could make the same argument about prostitution and sex, but then again, I don't believe that should be illegal either. I guess, it comes down to the "a society where everyone is blackmailing each other tends to be bad and lead to worse acts" but I'm not sure I'm convinced.

You don't need silly long words to solve anything, really. It's surprisingly easy, when you come to look at it though, quite a nice solution for a seemingly convoluted problem.

 

Solving through truth tables just seems incredibly boring to me, it's like getting an ugly numerical solution when you could get a nice exact one (except that it's the process that is different, rather than the end result).

There's also the issue that as you add more and more variables, basic truth tables become completely infeasible.

Simplify applyin' properties: [math](p\implies q)\implies[p\implies(\sim q\wedge p)].[/math]

One thing to remember is that [math]a \implies b \equiv a \wedge \neg b [/math], so then you can just apply that, demorgan's law and some of the other basic rules and derive a rather short equivalent formula.