Let's see. The notes in E Maj. are:

E F# G# A B C# D#

Which leads us to:

452?371
753?243

That Octave F# would be known as a 9th note, but I don't really follow the clue.

Also, you'll notice the C doesn't fall into the scale he's using. Maybe that one was misheard. (I don't really have a good ear, so I'm not going to venture a guess.) Also, for completeness' sake, C is the only note between B and C#; that is, there's no such thing as B#. (Those of you who know why that's not 100% true, keep it to yourselves; that information isn't going to help here.)